# Congruence Classes

by Juanriq
Tags: classes, congruence
 P: 42 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 $[b] \in \thinspace \mathbb{Z}_n$ such that $[a][b] = 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][b] = [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][b] = [1] implies [ab] = [1]. Can I say that [0] = [n], so [1] = [n+1] = [n] + [1], therefore [ab] - [n] = [1]? Thanks in advance!