2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 11, 2017 at 23:20
  • $\begingroup$ Sharp. Yes, I read over that. $\endgroup$ Feb 12, 2017 at 5:39

6 Answers 6

5
$\begingroup$

Hint $\ $ Simpler: $\ k \equiv k(ak') = (ka)k'\equiv k'$ is about as simple as it gets. Motivation is here.

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$

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$ Feb 11, 2017 at 18:00
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 11, 2017 at 21:12
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Feb 11, 2017 at 16:19
  • $\begingroup$ @GarthMarenghi See my edit. Hope it helps. $\endgroup$ Feb 12, 2017 at 0:53
0
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ It would be very helpful to me if know what is fault. Please. Just tell, would delete it. $\endgroup$
    – jiten
    Jun 9, 2022 at 15:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .