Modular Arithmetic Inverse Proof

Question

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

score 2 · Answer 1 · answered Feb 19 '21 at 07:59

2

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

answered Feb 19 '21 at 07:59

Wuestenfux

20,964

Right... Thanks – Jumping Juniper Feb 19 '21 at 08:30
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) – Jumping Juniper Feb 19 '21 at 11:18
Its maybe better to ask a new question. – Wuestenfux Feb 19 '21 at 11:22

score 1 · Answer 2 · answered Feb 19 '21 at 07:54

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

Modular Arithmetic Inverse Proof

2 Answers2