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.