Congruence Classes

Juanriq

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

1. The problem statement, all variables and given/known data
Let n be an integer and let [latex] [a] \in \thinspace \mathbb{Z}_n [/latex]. Prove that there exists and element [latex][b] \in \thinspace \mathbb{Z}_n[/latex] such that [latex][a][b] = 1[/latex] if and only if [latex]\gcd (a,n) = 1[/latex].


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



Now, for the other implications... uh little lost. [a][b] = [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.