Expert: Sherry Wallin - 12/11/2008

Question
Prove that the non-zero element [a] of Z(integers)sub n, has a multiplicative inverse in Z(integers)sub n if and only if n and a are relatively prime; that is, the greatest common divisor of n and a is 1.

Answer
Hi Pete~
    Ok, let's make a stab at it:

(-->) Suppose a,b != 0 in Z_n such that ab = 1 mod n then n|(ab-1) -->there exists a k in Z such that ab-1 = nk -> ab - nk = 1 -->(a,n)= 1.

(<--) Now suppose (a,n) = 1 then there exists an x,y in Z such that
ax + ny = 1 --> ny = 1-ax -> n|(1-ax) 1-ax = 0 mod n -> 1 = ax mod n --> x = a^-1

Of course you now want to draw your conclusion.

Note: I used "=" signs for congruence. Also about notation: (a,n) is the same as gcd(a,n) which is the same as the greatest common divisor of a and n

I hope this is clear for you.

Math Prof