Proof that if $a$ is coprime to $n$ in $R = \mathbb{Z}/(n)$, then $a$ is a unit Proof that if $a$ is coprime to $n$ in $R = \mathbb{Z}/(n)$, then $a$ is  a unit
Let $a \in R$ be coprime to $n$.
Then $gcd(a, n) = 1$
$\implies a\nmid n$
Let $b \in R$.
Now as $a \nmid n$ we have that $ba \neq 0$
I.e. $ba \in \{1,...,n-1\}$
I.e. ba will eventually 'hit' all numbers in $\{1, 2, ...n-1\}$, and in particular for some value of $b$ we will get that $ba = 1$.
 A: Your proof is wrong.


*

*You deduce everything from the statement $a \not\mid n$. This is intuitively wrong: for example $4 \not\mid 6$, but 4 is not a unit in $\mathbb{Z}/(6)$.

*Even though $a \not\mid n$, it is possible that there is a $b$ such that $ba = 0$ in $\mathbb{Z}/(n)$. For example, $3 \cdot 4 = 12 \equiv 0 \pmod{6}$.

*How do you prove that $ba$ will eventually hit all the numbers in $\{1,...,n-1\}$?


The best way to prove this fact is Bezout's theorem.
A: Your approach doesn't quite work. Take $n=12$ and $a=9$. $9\nmid 12$ but $9\cdot 4\equiv 0$.
If $\gcd(a,n)=1$, you find $x$ and $y$ so that $ax+ny=1$ (why?).
Now reduce the equation modulo $n$. You see that $\bar a\bar x+\bar 0=1$. So $\bar x$ is an inverse for $\bar a$ in $\mathbb Z/(n)$.
A: Not to answer a question with another question, but:
What about the old saw that $\gcd(a, n) = 1$ implies there exist $c, d \in \Bbb Z$ with $ac + dn =1$ whence, reducing $\mod n$, we have $ac = 1$ in $R$, so $a$ is a unit in $R$?
Hmmm . . . I guess that's the Bezout's identity approach . . . just checked out robjohn's comment.
Hope this helps.  Cheerio,
and as always,
Fiat Lux!!!
