# Modular Arithmetic Inverse Proof

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

## 2 Answers

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

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

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