Modular Inverses
Modular Arithmetic
by Equation Tracker
1 Inverses
Theorem 1.1 (Modular Inverses). Let p be a prime and a be an integer coprime to
p. Then there always exists an integer x such that
ax ≡ 1 (mod p)
This integer x is called the inverse of a modulo p.
This is an extremely useful Theorem in Number Theory. Modular inverses have
a lot of nice properties. Some properties of Modular Inverses are given below. We
denote the inverse of a as a−1 .
• Inverses behave like fractions. i.e.
a c ad + bc
+ ≡ a · b−1 + c · d−1 ≡ (ad + bc) · (bd)−1 ≡ (mod p)
b d bd
and
a c ac
· ≡ (a · b−1 ) · (c · d−1 ) ≡ (ac) · (bd)−1 ≡ (mod p)
b d bd
• The inverse of an is the n-th power of the inverse of a. i.e.
n
(an )−1 ≡ a−1
• Not every integer has an inverse modulo m. An integer a has its inverse
modulo m if and only if gcd(a, m) = 1. We’ll prove this later.
• If gcd(a, m) = 1, then there exists a unique inverse x of a such that 0 < x < m.
Before Proving anything, let’s define general inverse for modulo n. Here’s another
property that is left for the readers as an exercise.
Problem 1.1
Prove that, if a ̸≡ 0 (mod p), then
ap−2 ≡ a−1 (mod p)
1
2 General Inverses
Theorem 2.1. Let n ≥ 2 be any positive integer. Then every number a with
gcd(a, n) = 1 has an unique inverse 0 < x < n such that
ax ≡ 1 (mod n)
We write x = a−1 .
Proof. Consider the following set
S = {a, 2a, 3a, . . . , (n − 1)a}
Suppose there exists two elements ak and al in this set such that
ak ≡ al (mod n) and k > l
. Now
ak ≡ al (mod n) =⇒ n | a(k − l) =⇒ n | k − l
which is a contradiction because 0 < (k − l) < n. Hence, we can say that every
element in this set has a unique remainder when divided by n.
Notice that, am ̸≡ 0 (mod n) where am ∈ S. Therefore, it is obvious that,
{a, 2a, 3a, . . . , (n − 1)a} ≡ {1, 2, 3, . . . , (n − 1)} (mod n)
and this ends our proof.
This is an amazing theorem. We can now divide modulo any number, well
almost. In fact, we have only proved that if gcd(a, n) = 1, then a has an inverse.
What if gcd(a, n) ̸= 1? Does an inverse exist in that case?
Lemma 2.1.1. If n is a natural number, and a is an integer, then a has an inverse
modulo n if and only if gcd(a, n) = 1. In particular, if gcd(a, n) > 1, then a does
not have an inverse.
Proof. Let gcd(a, n) = d. Assume that x is the inverse of a modulo n. So, a = da′
and we’ve,
ax ≡ 1 (mod n) =⇒ n | ax − 1 =⇒ d | da′ x − 1 =⇒ d | 1
Which forces d = 1 and we are done.
Lastly, here’s an easy exercise for the readers.
Problem 2.1: Sum of inverses
Prove that,
1−1 + 2−1 + · · · + (n − 1)−1 ≡ (1 + 2 + · · · + (n − 1))
(mod n)