Prove that an integer cannot have more than one inverse for a given modulus.

"First, we note that an integer cannot have an inverse at all unless the integer is relatively prime to the modulus. Now, let $a$ be an integer that is relatively prime to a modulus $m$. Let $k_1$ and $k_2$ be distinct modulo-$m$ residues. Consider the difference between $ak_1$ and $ak_2$: $$ak_1 - ak_2 = a(k_1 - k_2).$$Since $k_1$ and $k_2$ are distinct modulo-$m$ residues, their difference is not a multiple of $m$. Since $a$ is relatively prime to $m$, $a(k_1 - k_2)$ is not a multiple of $m$. This means that $ak_1 \not\equiv ak_2 \pmod{m}$. This means that the products of $a$ with each modulo-$m$ residue are incongruent modulo $m$, so only one of them can be congruent to 1 (mod $m$). Thus, $a$ does not have more than one modulo $m$ inverse."

I have two questions. The first one is: why do $k_1$ and $k_2$ be module-m residues?

And the second thing is, I would like to understand why only one of them can be congruent, in the simplest terms possible.

So let's say that I work in $\pmod{7}$. I choose an integer, $a$, to be relatively prime to 7: 11.

There are 6 residues when $\pmod{7}$: 0, 1, 2, 3, 4, 5, 6. I choose two distinct residues (3 and 6) and multiply them with $a$: $11 \cdot 6$ and $11 \cdot 3$. Now we have $66 \not \equiv 33 \pmod{7} \Rightarrow 3 \not \equiv 5 \pmod{7}$.

"This means that each product is equivalent to a different modulo-m residue, one of which is 1." But this isn't the case, 3 and 5 are not 1.

• Note that the original says "only one of them can be 1" (but "can" doesn't mean it actually happens), while your paraphrase "one of which is 1" changes the meaning. Feb 11, 2017 at 23:20
• Sharp. Yes, I read over that. Feb 12, 2017 at 5:39

Hint $\$ As for simpler proofs, $\ k \equiv k(ak') = (ka)k'\equiv k'$ is about as simple as it gets.

The idea behind your proof is clarified if you ponder the following chain of equivalences mod $n$.

$\qquad\ \ ab\equiv 1\ \ {\rm for\ some}\ b$
$\iff a\mapsto ax\ \ \rm is\ onto.\ \ \ Proof\!:\ (\Leftarrow)\ \ clear.\ \ (\Rightarrow)\ \ c \equiv a(bc).$
$\iff a\mapsto ax\ \ \rm is\,\ 1\!-\!1,\ \$ since, by pigeonholing, a map on a finite set is onto $\!\iff\!1\!-\!1$
$\iff \ker(a\mapsto ax) = 0$
$\iff ax\equiv 0\,\Rightarrow\, x\equiv 0$
$\iff\ n\mid ax\,\Rightarrow\ n\mid x$
$\iff (n,a) = 1$

We are working in some ring, so inverses have to be modulo $m$ residues because that is what is in the ring. Then they assume there are two and reach a contradiction. If they are both inverses we have $ak_1 \equiv ak_2\equiv 1.$ which gives $a(k_1-k_2)\equiv 0$ Since $a$ is coprime to the modulus, we must have $k_1-k_2 \equiv 0$.

• I am sorry, I am not familiar with the concept of ring. I assume with ring that you mean modulo-m system, i.e. something akin to equivalency classes. -- Though I read your answer a couple of times, I am still not understanding. In particular, what the contradiction exactly is. -- "Then they assume there are two". I am missing out what these two are. At first I thought inverses, but in the next sentence you say "if they are both inverses". -- So what if they are? How does this mean that $ak_1 \equiv ak_2 \equiv 1$? Sorry for the ignorance! Feb 11, 2017 at 18:00
• A ring is an abstract algebraic system that generalizes the integers. In a ring you can add, subtract, and multiply, but not necessarily divide, and distribute multiplication over addition just like the integers. Any modulo system forms a ring. Yes, they assume there are two different inverses and name them $k_1$ and $k_2$. They reach a contradiction. In your example, you have chosen $a=11$. You should then be looking for an inverse and can find that $2$ is the inverse of $11$ because $2 \cdot 11 \equiv 1 \pmod 7$, but there is not another one. Feb 11, 2017 at 21:12

Let $a\in \mathbb Z/n\mathbb Z$ a unit. Then there is $k\in \mathbb Z/n\mathbb Z$ s.t. $$ak=1.$$ Suppose $k'\in \mathbb Z/n\mathbb Z$ is s.t. $$ak=ak'=1.$$ In particular, $a(k-k')=0$ and thus $n\mid a(k-k')$. Since $a$ is a unit, $\gcd(n,a)=1$ and thus $n\mid k-k'$. In particular, $k-k'=0$ in $\mathbb Z/n\mathbb Z$ and thus $k=k'$ in $\mathbb Z/n\mathbb Z$.

I think the simplest terms possible will have to use this theorem or something essentially equivalent:

If $a$ and $m$ are relatively prime and $a$ divides $mn$ then $a$ divides $n$.

That's a generalization of the theorem that if a prime divides a product then it divides (at least) one of the factors.

Now it's easy: if $k_1$ and $k_2$ are both inverses of $a$ modulo $m$ then $m$ divides $ak_1 - ak_2 = a(k_1-k_2)$ since that's just $1 - 1 \equiv 0 \pmod{m}$. Since $a$ and $m$ are relatively prime, $m$ divides $k_1-k_2$. That says the two inverses are congruent modulo $m$. That means that modulo $m$ the inverse is unique.

Edit in response to OP's comment.

I didn't closely follow the argument you posted - I wrote a different one that depends on the same crucial fact.

Here's how I might clarify the part of your argument that begins "Let $k_1$ and $k_2$ be distinct $\ldots$"

I claim that if $ak_1 \equiv ak_2 \pmod{m}$ then $k_1$ and $k_2$ must be congruent modulo $m$. That's because $$ak_1 \equiv ak_2 \pmod{m}$$ implies $$m \text{ divides } a(k_1 - k_2) .$$ Since $a$ and $m$ are relatively prime, $m$ must divide $k_1 - k_2$ so $k_1$ and $k_2$ are congruent modulo $m$.

That's actually stronger than you need for this application. The uniqueness of the inverse is a special case: you can't have two different resides $k$ both of which satisfy $ak \equiv 1 \pmod{m}$.

• I feel your answer clicks the most, mostly because the theorem you speak of is indeed what preceded the paragraph I posted. -- You mention that if $k_1$ and $k_2$ are both inverses of $a$ modulo $m$ (sic), but how did you get that from what I posted? I do not see a mention of them both being inverses, only that they are distinct residues modulo $m$. -- I follow mostly everything you are saying, but the last sentence still trips me up a bit. I still am a bit lost as to why this means that the inverse is unique Feb 11, 2017 at 16:19
• @GarthMarenghi See my edit. Hope it helps. Feb 12, 2017 at 0:53

For the first question, "why do $k_1$ and $k_2$ be module-$m$ residues," the answer is because when we use the set of module-$m$ residues, the proof works:

Since $k_1$ and $k_2$ are distinct modulo-$m$ residues, their difference is not a multiple of $m$.

If we let $k_1$ and $k_2$ be any two distinct integers, we would not be able to say their difference is not a multiple of $m.$ There are plenty of pairs of distinct integers whose difference is a multiple of $m.$

But we don't need to make a statement about any two integers; the thing that we want to prove is just a statement about residues modulo $m.$ So those are what we use.

For the second question, really you seem to be asking why this is true:

This means that the products of $a$ with each modulo-$m$ residue are incongruent modulo $m$, so only one of them can be congruent to 1 (mod $m$).

The key point is to figure out what this statement means. It doesn't say there is any modulo-$m$ residue whose product with $a$ is congruent to $1.$ It merely says that there cannot be more than one such residue.

The justification for this claim is that if $a$ has an inverse, that is, if there is a modulo-$m$ residue whose product with $a$ is congruent to $1,$ let's use that residue as $k_1$ (so we have $ak_1\equiv 1 \pmod m$). Then if $k_2$ is any other residue different from $k_1,$ the previous part of the proof shows that $ak_2 \not\equiv ak_1 \pmod m,$ but since $ak_1\equiv 1 \pmod m,$ it follows that $ak_2 \not\equiv 1 \pmod m,$ and $k_2$ is not an inverse. In short, if we find a residue that is an inverse of $a,$ that's it; there are no others.

And that means at most one inverse for $a$ from among all the residues modulo $m.$

Since this particular statement did not claim that there is always an inverse of $a$ modulo $m$ if $a$ is relatively prime to $m,$ you should expect to see a proof of that fact somewhere else.

As for the example with $m=7$ and $a=11,$ there are seven different residues modulo $m,$ and only one of those can be an inverse of $11$; there are six other residues that cannot be inverses of $11.$ So if you now choose two of the seven residues modulo $m,$ if you choose them at random you will very likely choose two of the six that are not inverses of $11.$ It is therefore not at all surprising that neither of the two you actually did pick was an inverse.

Under multiplication operation $$\times$$(with meaning derived from integer multiplication), any integer in set of equivalence classes $$\{0,1,..,m-1\}$$ has an inverse iff (or, just if ?) it is relatively prime to the modulus $$m$$. Now, let $$a$$ be an integer that is relatively prime to a modulus $$m$$. Let $$k_1, k_2$$ be distinct modulo-$$m$$ integers in the set.

$$ak_1 - ak_2 = a(k_1 - k_2).$$

Also, $$(k_1 - k_2)\ne km$$ for any integer $$k$$.

Note: $$0\lt k= \frac{(k_1 - k_2)} m \lt 1$$.

As $$(a,m)=1, a(k_1 - k_2)\ne km$$.

This means that $$ak_1 \not\equiv ak_2 \pmod{m}$$. This means that the products of $$a$$ with each modulo-$$m$$ residue are incongruent modulo $$m$$, so only one of them can be congruent to 1 (mod $$m$$). Thus, $$a$$ does not have more than one modulo $$m$$ inverse.

$$k_1, k_2$$ must lie obviously in the set of remainder equivalence classes, else it is possible that $$\overline{k_1}=\overline{k_2}$$. Then the distinct values of $$\overline{k_1}, \overline{k_2}$$ cannot be guaranteed.

As a side-effect, only then $$0\lt k\lt 1$$. Else, $$k=0$$.

• It would be very helpful to me if know what is fault. Please. Just tell, would delete it. Jun 9 at 15:20