2
$\begingroup$

Let $n$ be an integer and $i\in \{1,\cdots,n-1\}$. I want to show that $i$ is invertible in $\mathbb Z_n$ if and only if $i$ is coprime to $n$.

One way is easy. suppose $i$ is coprime to $n$ then $\alpha i +\beta n=1$ for some $\alpha,\beta \in \mathbb Z$, so $\alpha i =1 - \beta n$ hence $\alpha i \equiv 1 (mod\; n)$ and $i$ is invertible.

the other way is less obvious to me. suppose that $i$ is invertible in $\mathbb Z_n$. Why it must be coprime to $n$? my guess: suppose they are not coprime then $i=da$ and $n=db$ for some $d>1,a,b$ but since $i$ is invertible then $li=1+mn$ for some $l,m$ hence $lda=1+mdb$ so $d(la-mb)=1$ this implies that $d=\pm 1$ which is impossible since $d>1$

is this correct and is there more conceptual argument for this?

  • 2
    This is correct. Another way of saying this is that the gcd of $i$ and $n$ is the smallest (in absolute value) integer, expressible as a linear combination of $i$ and $n$.2011-11-15

2 Answers 2

1

Your argument works perfectly well. A variant with a more abstract flavour that uses your notation is to observe that $ib=(ad)b=a(db)=an$ so $ib \equiv 0 \pmod{n}$.

If $j$ were an inverse of $i$, then we would have $j(ib)\equiv j\cdot 0\equiv 0\pmod{n}.$ But $j(ib)=(ji)b\equiv b\pmod{n}.$ Thus $b\equiv 0 \pmod{n}$, which is impossible if $d>1$, since then $0.

1

My intuition is along the lines of your second argument: if $i=da$ and $n=db$, all integer multiples of $i$ must be multiples of $d$ and hence can never be one plus a mutiple of $d$.