Expert: Paul Klarreich - 12/9/2008

Question
Prove that the nonzero element [a] of Zn has a multiplicative inverse Zn if and only if n and a are relatively prime; that is, the great common divisor of n and a is 1.

(Im not able to show it on here but the Z is in bold, and it is sub n, you know little n below the bold Z)

I have no idea where to start on this question,  if you could help start me off and just give me a few hints from there that would be great!

Answer
Questioner:   sam
Category:  Advanced Math
Private:  No
 
Subject:  Proof help please
Question:  Prove that the nonzero element [a] of Zn has a multiplicative inverse Zn if and only if n and a are relatively prime; that is, the great common divisor of n and a is 1.

(Im not able to show it on here but the Z is in bold, and it is sub n, you know little n below the bold Z)

I have no idea where to start on this question,  if you could help start me off and just give me a few hints from there that would be great!
....................
Hi, Sam,

A good place to start is in making sure you have defined your terms.  I am going to assume that you mean:

Z[n] is the ring of integers modulo n.

So you want to prove that if  gcd(a,n) = 1, then there exists x such that  ax == 1 mod n.  ('==' means congruent to.)

There is a well-known theorem of elementary number theory that says:

If gcd(a,b) = k, then there exist integers x,y, such that
ax + by = k.

Naturally you want the form of this that has  k = 1.  

I think you should be able to do something with that.