Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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$. –  Miha Habič Nov 15 '11 at 9:56

2 Answers 2

up vote 1 down vote accepted

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<b<n$.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.