Lesson 3 of 8 · Number Theory
Modular Arithmetic
Modular arithmetic lets you answer "what's the remainder" or "what's the units digit" questions about enormous numbers without ever computing the full value. The key habit is reducing early and often — never carry a number bigger than the modulus through more than one operation.
Mark your status for this lesson:
Learning objectives
- Reduce sums, differences, and products modulo m by reducing each term first, not the final result.
- Find the units digit of a power by identifying its short repeating cycle.
- Compute large modular exponents efficiently by finding and using the cycle length.
- Apply the digit-sum shortcut for divisibility and remainders mod 9.
The core idea
a ≡ b (mod m) means m divides (a − b) — equivalently, a and b leave the same remainder when divided by m. The power of modular arithmetic is that addition, subtraction, and multiplication all respect this equivalence: you can reduce numbers mod m at any point in a calculation, not just at the very end, and the final answer is unaffected.
Modular arithmetic respects +, −, ×
(a+b) mod m = [(a mod m) + (b mod m)] mod m
Same pattern holds for subtraction and multiplication. This is why you can reduce huge numbers to small remainders before ever combining them.
Finding a power's cycle
Compute successive powers of the base mod m: a¹, a², a³, ... mod m. Since there are only m possible remainders, the sequence must eventually repeat — usually quickly. Once you know the cycle length, reduce the exponent mod that length to find any power instantly.
Digit-sum shortcut (mod 9 and mod 3)
n ≡ (sum of its digits) (mod 9)
Because 10 ≡ 1 (mod 9), every power of 10 also reduces to 1 mod 9 — so a number's remainder mod 9 equals its digit sum's remainder mod 9. The same trick works mod 3.
Worked example 1 — Reducing before combining
Problem
Find the remainder when 1,847 × 2,913 is divided by 6.
Key insight
Reduce each factor mod 6 before multiplying — you never need the actual product.
Solution
1847 ≡ 5, 2913 ≡ 3 (mod 6). 5 × 3 = 15 ≡ 3 (mod 6). Remainder: 3.
Takeaway
Reducing first avoids ever multiplying the full four-digit numbers together.
Worked example 2 — Finding a units-digit cycle
Problem
Find the units digit of 4²⁰²⁵.
Key insight
The units digits of powers of 4 cycle: 4, 6, 4, 6, .... Just determine whether 2025 is odd or even.
Solution
Odd powers of 4 end in 4, even powers end in 6. Since 2025 is odd, the units digit of 4²⁰²⁵ is 4.
Takeaway
Cycle lengths for units digits are always short (1, 2, or 4) — always find the cycle before trying to compute anything about a huge exponent directly.
Worked example 3 — Modular exponentiation via cycle
Problem
Find 5³⁰ mod 7.
Key insight
Compute the first several powers of 5 mod 7 to find the repeating cycle.
Solution
Powers of 5 mod 7: 5, 4, 6, 2, 3, 1 — then it repeats, so the cycle length is 6. 30 mod 6 = 0, meaning 5³⁰ ≡ 5⁶ ≡ 1 (mod 7).
Takeaway
When the exponent is an exact multiple of the cycle length, the result is whatever the last term in the cycle is — here, 1.
Worked example 4 — The digit-sum shortcut
Problem
Find the remainder when 78,912 is divided by 9.
Key insight
A number's remainder mod 9 equals the remainder of its digit sum mod 9.
Solution
Digit sum: 7+8+9+1+2 = 27, and 27 mod 9 = 0. So 78,912 is divisible by 9, remainder 0.
Takeaway
This shortcut works because 10 ≡ 1 (mod 9) — every place value contributes exactly its digit, nothing more, to the sum mod 9.
Strategy notes
Reduce early, reduce often
Never let an intermediate result grow larger than necessary — reduce mod m after every addition or multiplication, not just at the very end.
Always look for the cycle before computing a large power
Any "find the units digit" or "find aⁿ mod m" question wants you to find the short repeating cycle of the base's powers, then reduce the exponent mod the cycle length — never try to compute the power directly.
Common mistakes
Reporting a negative remainder
A remainder is always in the range 0 to m−1. If a computation gives a negative result, add multiples of m until it lands in the correct range.
Confusing cycle length with the exponent itself
Once you find a cycle of length k, reduce the exponent mod k — and remember that if the reduced exponent is 0, the answer corresponds to the last term in the cycle, not to a¹.
Applying the digit-sum shortcut to the wrong modulus
The digit-sum trick works for mod 9 and mod 3 specifically (because 10 ≡ 1 mod 9 and mod 3). It does not work for other moduli like 7 or 11 — those need different tricks entirely.
Practice
20 questions across four difficulty tiers, each with a single numeric answer. Up to three tries per question before the solution is shown.