Thread: Multiplicative inverse question

  1. #1
    Banned
    Join Date
    May 2007
    Location
    Berkeley, CA
    Posts
    329

    Multiplicative inverse question

    If I have the additive group (Z_65536,+) (i.e. integers between 0 and 65535 together with addition modulo 65536).

    How does Z_65536 does *not* form a group together with multiplication modulo 65536? Someone told me that no all integers have multiplicative inverses.

    They tod me that 3 does have a multiplicative inverse in Z_65536, and it is in fact 43691. How do they get this number? Then then told me that 4 doesn't have a multiplicative inverse in Z_65536.

    How did they do these calculuations?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Z_p is never a group under *. Z_p - 0 is a group if p is prime. It's pretty clear that 65536 is not prime. Since 4 is even, k*4 is also even, hence can never be 1 (since reduction by an even modulus will preserve parity).

    As for 3, you're looking for numbers k and m such that 3k = 1+65536m. Look up Chinese Remainder Theorem.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Not a C question - moved.
    Not really a programming related question either, perhaps a math forum would be better?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Salem View Post
    Not a C question - moved.
    Not really a programming related question either, perhaps a math forum would be better?
    It's programming-related. The compiler will often find the multiplicative inverse in order to translate a division by a constant into a multiplication by a constant, which is faster of course.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  2. Confuted/Blackrat: quaternion question
    By Silvercord in forum Game Programming
    Replies: 12
    Last Post: 08-18-2003, 06:02 PM
  3. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  4. Question about linked lists.
    By cheeisme123 in forum C++ Programming
    Replies: 6
    Last Post: 02-25-2003, 01:36 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 01:47 AM