# Congruence Classes

1. Oct 17, 2010

### 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 $[a] \in \thinspace \mathbb{Z}_n$. Prove that there exists and element $\in \thinspace \mathbb{Z}_n$ such that $[a] = 1$ 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]?

2. Oct 18, 2010

### Tedjn

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

3. Oct 18, 2010

### Juanriq

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

4. Oct 18, 2010

### 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.