1
$\begingroup$

Let $m, x$ be positive integers such that $\gcd(m, x) = 1$. Then $x$ has a multiplicative inverse modulo $m$, and it is unique (modulo $m$).

Proof: Consider the sequence of $m$ numbers $0, x, 2x, \dots, (m−1)x$. We claim that these are all distinct modulo $m$. Since there are only $m$ distinct values modulo $m$, it must then be the case that $ax \equiv 1 \pmod m$ for exactly one $a$ (modulo $m$). This $a$ is the unique multiplicative inverse of $x$.

To verify the above claim, suppose for contradiction that $ax \equiv bx \pmod m$ for two distinct values $a,b$ in the range $0 \leq b \leq a \leq m−1$. Then we would have $(a−b)x \equiv 0 \pmod m$, or equivalently, $(a−b)x = km$ for some integer $k$ (possibly zero or negative). However, $x$ and $m$ are relatively prime, so $x$ cannot share any factors with $m$. This implies that $a−b$ must be an integer multiple of $m$. This is not possible, since $a−b$ ranges between $1$ and $m−1$.


I understand the contradiction and how this proves that the sequence of $m$ numbers are all unique mod $m$; however, I am unsure how if this is the case, then it implies that $ax \equiv 1 \pmod m$ for exactly one $a \pmod m$.

$\endgroup$
1
$\begingroup$

''however, I am unsure how if this is the case, then it implies that ax≡1 (mod m) for exactly one a (mod m)''

Its in the proof. It shows that there exists an $a$ with $ax\equiv 1\mod m$ and since the values $0,x,2x,\ldots,(m-1)x$ are all distinct, there is exactly one $a$.

$\endgroup$
3
  • $\begingroup$ Right... Thanks $\endgroup$ – Jumping Juniper Feb 19 at 8:30
  • $\begingroup$ Follow-up question: Can you clarify how this proof can be used to show that every non-zero integer from 1 to (p-1) , where p is a prime number, has an inverse (mod p)? (Context: I am trying to ultimately understand Fermat's Little Theorem) $\endgroup$ – Jumping Juniper Feb 19 at 11:18
  • $\begingroup$ Its maybe better to ask a new question. $\endgroup$ – Wuestenfux Feb 19 at 11:22
0
$\begingroup$

If we let $S$ denote the set of residue classes modulo $m$, then the map $a\mapsto ax\pmod m$ is a function from $S$ to itself. The claim shows that this function is injective. This injectivity already shows that $ax\equiv1\pmod m$ for at most one residue class $a\pmod m$.

But since $S$ is finite, any injective function from $S$ to itself is automatically surjective (this is basically the pigeonhole principle). And surjectivity implies that $ax\equiv1\pmod m$ for at least one residue class $a\pmod m$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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