Proving Congruence Classes: [a][b]=1 iff gcd(a,n)=1

[Juanriq]

Salutations! I believe I have one implications correct and I am looking for a push in the right direction for the other.

Homework Statement

Let n be an integer and let [a] \in \thinspace \mathbb{Z}_n. Prove that there exists and element <b> \in \thinspace \mathbb{Z}_n</b> such that [a]<b> = 1</b> if and only if \gcd (a,n) = 1.


2. The attempt at a solution
For the (\Longleftarrow)case, we know that the \gcd( a, n ) = 1 and we are trying to show [a] = [1] in \mathbb{Z}_n We know that \exists x,y \in \mathbb{Z} such that
ax + ny = 1 \Longrightarrow ax - 1 = -ny but this implies that a b - 1 = vy , where x = b and v = -n and also v| ab - 1.



Now, for the other implications... uh little lost. [a] = [1] implies [ab] = [1]. Can I say that [0] = [n], so [1] = [n+1] = [n] + [1], therefore [ab] - [n] = [1]?

Thanks in advance!

 

[Tedjn]

You have [ab] = [1] in Z_n. What does that mean in Z?

 

[Juanriq]

In Z, it would mean that b is the multiplicative inverse of a, right? In Z we would just have ab = 1

 

[Tedjn]

Yes, if ab = 1 in Z, that's right. What I actually wanted was for you to translate this statement as is into Z; that is, tell me what this equivalence class equality means. You've already done this to prove the backwards implication, so you know how. But it's the right place to start.