Discrete Math · Undergraduate
Modular Arithmetic and Congruences
Quick answer
Two integers are congruent modulo n, written a ≡ b (mod n), when they leave the same remainder on division by n, or equivalently when n divides a − b. Congruences can be added and multiplied like equations, so large numbers can be reduced to small remainders before any arithmetic is done. That makes questions about huge powers, last digits and days of the week quick to answer. Division works when the divisor has an inverse mod n, which happens exactly when it shares no factor with n.
What you'll learn
- Compute remainders and write congruences
- Reduce sums, products and powers modulo n
- Find last digits and future days of the week
- Find a modular inverse and solve ax ≡ b (mod n)
Clock arithmetic
Ten hours after o’clock it is o’clock, not . A clock keeps only the remainder after dividing by . Modular arithmetic does the same with any number , the modulus.
We say is congruent to modulo ,
when and leave the same remainder on division by , or equivalently when divides . For example , since is a multiple of .
Why you can reduce first
If and , write and . Then
and sums work the same way. The extra multiples of never affect the remainder, so any number may be replaced by its remainder at any point in a calculation. That is what makes huge computations small: you never have to handle a number bigger than .
Worked examples
An inverse of mod exists exactly when and share no factor greater than . The number has no inverse mod : is always even, and no even number is .
Common mistakes
Practice problems
-
Find .
Answer
Full solution
.
-
Find .
Answer
Full solution
.
-
Find .
Answer
Full solution
, and .
-
Find .
Answer
Full solution
, and .
-
Find the inverse of modulo .
Answer
Full solution
.
-
Solve .
Answer
Full solution
The inverse of is , since . So . Check: .
-
Today is Friday. What day is it days from now?
Answer
Thursday
Full solution
, so it is days after Friday.
-
A student computes as . What went wrong?
Answer
Exponents cannot be reduced mod ; the answer is .
Full solution
Powers of repeat with period mod , not period , so the exponent reduces mod : , giving .
Frequently asked questions
What does a ≡ b (mod n) mean?
That a and b leave the same remainder when divided by n, or equivalently that n divides a − b. For example 17 ≡ 2 (mod 5).
Can you reduce numbers before multiplying?
Yes. If a ≡ a′ and b ≡ b′ (mod n), then a + b ≡ a′ + b′ and ab ≡ a′b′ (mod n). So replace each number by its remainder first.
How do you find a large power mod n?
Reduce as you go, and look for a power that is ≡ 1. Since 2³ = 8 ≡ 1 (mod 7), 2¹⁰⁰ = 2⁹⁹ · 2 ≡ 1 · 2 = 2 (mod 7).
What is a modular inverse?
A number x with ax ≡ 1 (mod n). It exists exactly when a and n have no common factor greater than 1. The inverse of 3 mod 7 is 5, since 15 ≡ 1.
How do you find the last digit of a power?
Work mod 10. The last digits of powers repeat in a short cycle; for 7 it is 7, 9, 3, 1, so 7^2026 ends in the same digit as 7², which is 9.