I am trying to prove that the only invertible elements in $\mathbb{Z}_n$ are those that are relatively prime to $n$.
The first half is straightforward. If $i$ is relatively prime to $n$, so $\gcd(i,n) = 1$, we have $\alpha i + \beta n = 1$, so $\alpha i – 1 = (-\beta)n$, so $\alpha i \equiv 1 \text{ mod $n$}$, and $a$ is the inverse of $i$.
The second half is less straightforward. I am trying to follow some proofs of this fact that I have found, but none of them are clear about the important step. Suppose $a$ is invertible. Then there exists $b$ such that $ab \equiv 1 \text{ mod $n$}$. So $ab – 1 = kn$ for some $k \in \mathbb{Z}$, so $ab = 1 + kn$. The claim at this point is that we can deduce immediately that $\gcd(a,n) = 1$. To show this, I believe we would need to show that $1$ divides both $a$ and $n$ (which is rather trivially true) and that if any other integer divides both $a$ and $n$, then it must divide $1$. Suppose $\gamma$ divides $a$ and $n$. That it divides $n$ implies that it implies $ab$, so it must divide $1 + kn$. It certainly divides $kn$ because it divides $n$, and it must also divide $1$, which gives the result.
How does this proof sound?
Best Answer
You proof is good. we can tie this all together:
$m$ is invertible $\mod n$ if and only if there is an integer $k$ so that $km \equiv 1\pmod n$ (Def)
if and only if $km -1$ is divisible by $n$ (Def)
if and only if there is an integer $j$ so that $jn = km-1$ (Def)
if and only if $km +(-j)n = 1$ (Obvious algebraic maniplation).
....
So we need to prove such $k,-j$ exist iff and only if $m,n$ are relatively prime.
....
If $m$ and $n$ are relatively prime the Bezout's lemma states precisely that such $k$ and $-j$ exist
And if such $k,-j$ exist then the $\gcd(m,n)$ divides the LHS so $\gcd(m,n)|1$ and so $\gcd(m,n) =1$. So $m$ and $n$ are relatively prime.