Multiplicative inverse question

[Overworked_PhD]

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?

[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.

[Salem]

Not a C question - moved.
Not really a programming related question either, perhaps a math forum would be better?

[brewbuck]

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.