In ordinary arithmetic, dividing by $a$ means multiplying by $1/a$. Mod $n$ there are no fractions, but sometimes there is a number that does the same job. Finding it uses Bézout's identity, and knowing when it exists fixes the trouble with cancelling we met in modular arithmetic.
Definition. An inverse of $a$ mod $n$ is an integer $x$ with $ax \equiv 1 \pmod{n}$. We write $x \equiv a^{-1} \pmod{n}$.
Theorem. $a$ has an inverse mod $n$ exactly when $\gcd(a, n) = 1$, and then the inverse is unique mod $n$.
💡 Why it works
$ax \equiv 1 \pmod{n}$ means $ax - 1 = ny$ for some integer $y$, that is, $ax - ny = 1$. If $\gcd(a, n) = 1$, Bézout gives such $x$ and $y$, so an inverse exists. If $d = \gcd(a, n) > 1$, then $d$ divides $ax - ny$, which would mean $d \mid 1$: impossible. Uniqueness: if $ax \equiv 1$ and $ax' \equiv 1$, then $x \equiv x(ax') = (ax)x' \equiv x' \pmod{n}$.
Arrows from $x$ to $2x \bmod 6$ reach only 0, 2 and 4, so no $x$ has $2x \equiv 1$: 2 has no inverse mod 6. With $a = 5$ every point is hit once, and $5 \cdot 5 = 25 \equiv 1$.
✏️ Worked example: Small modulus: try multiples
Find $3^{-1} \bmod 7$.
List $3x \bmod 7$: $3, 6, 2, 5, 1$ for $x = 1, 2, 3, 4, 5$.
$3 \cdot 5 = 15 = 2 \cdot 7 + 1 \equiv 1$.
Answer: $3^{-1} \equiv 5 \pmod{7}$.
✏️ Worked example: Larger modulus: extended Euclid
Find $17^{-1} \bmod 101$.
$101 = 17 \cdot 5 + 16$ and $17 = 16 \cdot 1 + 1$. The gcd is 1, so an inverse exists.
Mod 101 the multiple of 101 vanishes: $6 \cdot 17 \equiv 1$. Check: $102 = 101 + 1$.
Answer: $17^{-1} \equiv 6 \pmod{101}$.
✏️ Worked example: Dividing with an inverse
Solve $17x \equiv 5 \pmod{101}$.
Multiply both sides by $17^{-1} \equiv 6$: $x \equiv 6 \cdot 5 = 30 \pmod{101}$.
Check: $17 \cdot 30 = 510 = 5 \cdot 101 + 5$.
Answer: $x \equiv 30 \pmod{101}$.
Every nonzero residue mod the prime 11 has an inverse. They come in pairs (2 and 6, 3 and 4, 5 and 9, 7 and 8), and only 1 and 10 are their own inverses, a fact that returns in Wilson's theorem.
$a$
1
2
3
4
5
6
7
8
9
10
$a^{-1} \bmod 11$
1
6
4
3
9
2
8
7
5
10
⚠️ Common mistake
Expecting every nonzero number to have an inverse. Mod 6 the multiples of 2 are only $0, 2, 4$, so $2x \equiv 1$ has no solution: $\gcd(2, 6) = 2$. Before hunting for an inverse, check $\gcd(a, n) = 1$. Mod a prime $p$ the problem disappears: every $a$ with $p \nmid a$ has an inverse.
The numbers from 1 to $n$ that are coprime to $n$, and so have inverses, are called the units mod $n$. Counting them gives Euler's phi function.
🔑 Key idea
$a^{-1} \bmod n$ exists exactly when $\gcd(a, n) = 1$. Find it with the extended Euclidean algorithm: from $ax + ny = 1$, the inverse is $x \bmod n$.
Practice
Pass with 3 right answers, the last 2 in a row. Each right answer earns 2 XP.
William Stein, Elementary Number Theory: Primes, Congruences, and Secrets (Springer, 2009; free online edition), chapter 2, The Ring of Integers Modulo n (quickly computing inverses)
Lehman, Leighton and Meyer, Mathematics for Computer Science (MIT OpenCourseWare 6.042J), chapter on number theory: multiplicative inverses and cancelling