# Multiplicative inverse question

• 04-01-2008
Overworked_PhD
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?
• 04-01-2008
tabstop
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.
• 04-02-2008
Salem
Not a C question - moved.
Not really a programming related question either, perhaps a math forum would be better?
• 04-02-2008
brewbuck
Quote:

Originally Posted by Salem
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.