Modular Arithmetic in Ten Minutes: Remainders That Solve Equations
Last digits, divisibility, and equations that look impossible — almost all of them collapse once you stop tracking numbers and start tracking remainders.
Olympiad Desk · Core Learning
What you will take away
- a ≡ b (mod m) means m divides a − b — everything else follows
- You may add, subtract and multiply congruences freely; division needs care
- Power cycles are short: a^1, a^2, a^3 … repeats mod m after at most φ(m) steps
- A single mod equation is often enough to kill a whole expression
Modular arithmetic is bookkeeping with a coarse ruler. Instead of tracking a number, you track which tick mark it sits on, and that is frequently all a problem needs.
The only rule you need to remember
- If a ≡ b and c ≡ d, then a + c ≡ b + d and a·c ≡ b·d
- Powers follow: a^k ≡ b^k (mod m) for every positive integer k
- You can add, subtract or multiply both sides by anything — but only cancel a factor if it is coprime to m
Killing equations with one remainder
Many "prove there is no solution" problems are solved by choosing a modulus in which the two sides can never match. Squares mod 4 are 0 or 1; squares mod 8 are 0, 1 or 4; squares mod 3 are 0 or 1. Memorise those three lists and a large family of equations becomes trivial.
Powers come back around
Because there are only m remainders, the sequence a, a^2, a^3, … must repeat, and it starts repeating quickly. To find 7^2026 mod 10, list 7, 9, 3, 1 — period 4 — then reduce the exponent mod 4. No calculator, and no cleverness required.
Worked problems
- 1
Find the last digit of 7^2026.
Show hint
Work mod 10 and list the first few powers of 7 to find the cycle length.
Show solution
Powers of 7 mod 10 cycle as 7, 9, 3, 1 with period 4. Since 2026 = 4·506 + 2, the answer is the second term of the cycle.
Answer: The last digit is 9.
- 2
Prove that no perfect square can be written in the form 4k + 3.
Show hint
Square each of the four remainder classes mod 4 and look at the results.
Show solution
Every integer n is congruent to 0, 1, 2 or 3 mod 4. Then n² is congruent to 0, 1, 0 or 1 respectively — that is, n² ≡ 0 or 1 (mod 4). Since 4k + 3 ≡ 3 (mod 4) can never be 0 or 1, no perfect square has that form.
Answer: Squares are 0 or 1 mod 4, so 4k + 3 is impossible.
