Math Circle Lecture Plan | Ages 11–12 | Duration: 90 minutes (with break) | Topic: Modular Arithmetic & the Chinese Remainder Theorem
"What time is it 5 hours after 10 o'clock?"
Everyone knows the answer: 3 o'clock. But wait — $10 + 5 = 15$, not 3! What happened?
The clock "wraps around" after 12. We only care about the remainder when we divide by 12:
$$15 \div 12 = 1 \text{ remainder } 3$$Mathematicians write this as:
$$15 \equiv 3 \pmod{12}$$and read it as "15 is congruent to 3, mod 12."
| Question | Answer |
|---|---|
| $20 \bmod 12$ | $8$ (8 o'clock!) |
| $25 \bmod 12$ | $1$ |
| $100 \bmod 12$ | $4$ |
| $7 \bmod 7$ | $0$ (full wrap!) |
| $15 \bmod 5$ | $0$ |
| $17 \bmod 5$ | $2$ |
Imagine a combination lock with two rings, each showing numbers 0 to 9 (so 10 positions). There is one button. Every time you press it:
Ring A starts at 0, Ring B starts at 1.
Question: What is the fewest button presses to make both rings show the same number?
Ask kids to help fill this in, row by row, on the whiteboard:
| Presses ($n$) | Ring A: $n \bmod 10$ | Ring B: $(1 + 3n) \bmod 10$ | Match? |
|---|---|---|---|
| 0 | 0 | 1 | ✗ |
| 1 | 1 | 4 | ✗ |
| 2 | 2 | 7 | ✗ |
| 3 | 3 | 0 | ✗ |
| 4 | 4 | 3 | ✗ |
| 5 | 5 | 6 | ✗ |
| 6 | 6 | 9 | ✗ |
| 7 | 7 | 2 | ✗ |
| 8 | 8 | 5 | ✗ |
| 9 | 9 | 8 | ✗ |
| 10 | 0 | 1 | ✗ |
Hmm! After 10 presses we're back to the start. It seems like it never matches!
We need:
$$n \equiv 1 + 3n \pmod{10}$$Move things around:
$$n - 3n \equiv 1 \pmod{10}$$ $$-2n \equiv 1 \pmod{10}$$ $$2n \equiv -1 \equiv 9 \pmod{10}$$So we need $2n$ to end in 9. But $2n$ is always even, and 9 is odd. That can never happen!
Now let Ring B start at 0 instead of 1 (and still move 3 steps):
$$n \equiv 3n \pmod{10}$$ $$-2n \equiv 0 \pmod{10}$$ $$2n \equiv 0 \pmod{10}$$So $2n$ must be a multiple of 10: $n = 5, 10, 15, \ldots$
Discussion prompt: "Why did changing the starting position from 1 to 0 suddenly make it solvable?"
Now we have three rings, each with numbers 0 to 25 (26 positions). One button — all three move at once:
| Ring | Starts at | Steps per press |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 2 |
| 3 | 2 | 3 |
After $n$ presses:
| Ring | Shows |
|---|---|
| 1 | $n \bmod 26$ |
| 2 | $(1 + 2n) \bmod 26$ |
| 3 | $(2 + 3n) \bmod 26$ |
Question: What is the minimum number of presses so all three rings show the same number? Is it even possible?
We don't try to solve everything at once. Instead, we ask: when do two of them match? Then we check if the third agrees.
Subtract $2n$ from both sides:
$$-n \equiv 1 \pmod{26}$$Multiply both sides by $-1$:
$$n \equiv -1 \equiv 25 \pmod{26}$$Now here's a neat trick. Both sides and the modulus are all divisible by 2, so we can simplify:
$$n \equiv 12 \pmod{13}$$We need $n$ to be in both lists:
Look! 25 appears in both lists!
And there's a beautiful reason: 26 is a multiple of 13, so every number that's $25 \pmod{26}$ is automatically $12 \pmod{13}$ (because $25 = 1 \times 13 + 12$). The first condition already guarantees the second.
Verify together on the board:
Think of Ring 1 and Ring 2 like two runners on a circular 26-meter track. Ring 2 runs 1 m/s faster than Ring 1, and starts 1 meter ahead. For Ring 1 to "catch" Ring 2, it needs Ring 2 to lap around and come back — that takes 25 steps (one short of 26, because Ring 2 was already 1 ahead).
Ring 3 is 2 m/s faster and 2 meters ahead — proportionally the same chase! Everything aligns at the same moment.
In regular algebra, solving $3x = 12$ gives $x = 4$. Easy — just divide.
In mod-world, "division" is trickier. Let's solve:
$$3x \equiv 6 \pmod{9}$$Can we "divide by 3"? Both sides AND the modulus are divisible by 3:
$$x \equiv 2 \pmod{3}$$So $x = 2, 5, 8, 11, \ldots$ — three solutions in the range 0–8. ✓
Try: $2x \equiv 3 \pmod{6}$
Left side is always even, right side is odd. No solution!
Which of these have solutions? If yes, find the smallest $x \geq 0$.
| Equation | $\gcd$ | Solvable? | Solution |
|---|---|---|---|
| $3x \equiv 9 \pmod{12}$ | $\gcd(3,12)=3$, and $3 \mid 9$ ✓ | Yes | $x = 3$ |
| $4x \equiv 5 \pmod{6}$ | $\gcd(4,6)=2$, and $2 \nmid 5$ ✗ | No | — |
| $5x \equiv 3 \pmod{7}$ | $\gcd(5,7)=1$, and $1 \mid 3$ ✓ | Yes | $x = 2$ (since $10 \bmod 7 = 3$) |
| $7x \equiv 0 \pmod{14}$ | $\gcd(7,14)=7$, and $7 \mid 0$ ✓ | Yes | $x = 0$ (and $x = 2$) |
For the advanced/curious kids. This is the "boss level."
Over 1,500 years ago, the Chinese mathematician Sun Tzu (the math one, not the war one!) posed this puzzle:
A farmer counts eggs.
Counting by 3s, 2 are left over.
Counting by 5s, 3 are left over.
Counting by 7s, 2 are left over.
How many eggs?
In our notation:
$$x \equiv 2 \pmod{3}$$ $$x \equiv 3 \pmod{5}$$ $$x \equiv 2 \pmod{7}$$Step 1: Start with the first condition. $x \equiv 2 \pmod 3$, so:
$$x \in \{2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, \ldots\}$$Step 2: Which of those also satisfy $x \equiv 3 \pmod 5$? Check:
So $x \equiv 8 \pmod{15}$ (we combine the moduli: $3 \times 5 = 15$).
$$x \in \{8, 23, 38, 53, 68, 83, \ldots\}$$Step 3: Which also satisfy $x \equiv 2 \pmod 7$?
In the egg problem: 3, 5, and 7 share no common factors, so there's exactly one answer between 0 and $3 \times 5 \times 7 - 1 = 104$.
What if the moduli aren't coprime? Consider:
$$x \equiv 1 \pmod{4}$$ $$x \equiv 3 \pmod{6}$$Here $\gcd(4, 6) = 2 \neq 1$. The CRT doesn't directly apply. But a solution might still exist — we just need to be more careful.
List 1: $x \in \{1, 5, 9, 13, 17, 21, 25, \ldots\}$
List 2: $x \in \{3, 9, 15, 21, 27, \ldots\}$
Common values: $\{9, 21, 33, \ldots\}$, so $x \equiv 9 \pmod{12}$. It works!
But change it to:
$$x \equiv 1 \pmod{4}$$ $$x \equiv 2 \pmod{6}$$List 1: $\{1, 5, 9, 13, 17, 21, 25, 29, \ldots\}$ (all odd!)
List 2: $\{2, 8, 14, 20, 26, 32, \ldots\}$ (all even!)
Remember how our three-ring puzzle gave us:
$$n \equiv 25 \pmod{26}$$ $$n \equiv 12 \pmod{13}$$Here $26 = 2 \times 13$, so the moduli are not coprime. But we got lucky: the conditions were compatible ($25 \bmod 13 = 12$ ✓). The first condition was stricter and automatically implied the second.
If, instead, we had ended up with $n \equiv 25 \pmod{26}$ and $n \equiv 7 \pmod{13}$, that would be impossible — because $25 \bmod 13 = 12 \neq 7$.
Two rings, 0–11 (12 positions). Ring A starts at 0 and moves 1 step. Ring B starts at 4 and moves 5 steps. Find the smallest $n$ so both rings match, or prove it's impossible.
Hint: set up $n \equiv 4 + 5n \pmod{12}$ and simplify.
Sun Tzu's Variant: Find the smallest $x > 0$ such that:
$$x \equiv 1 \pmod{4}$$ $$x \equiv 2 \pmod{5}$$ $$x \equiv 3 \pmod{7}$$Hint: use the sieving method from Part 4.
Three rings, 0–29 (30 positions).
| Ring | Start | Step |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 3 | 4 |
| 3 | 5 | 7 |
Find the minimum $n$ for all three to match, or prove it's impossible.
Hint: you'll need the full CRT machinery for this one!
$n \equiv 4 + 5n \pmod{12}$
$-4n \equiv 4 \pmod{12}$
$4n \equiv -4 \equiv 8 \pmod{12}$
$\gcd(4, 12) = 4$, and $4 \mid 8$ ✓
Divide through by 4: $n \equiv 2 \pmod{3}$
Smallest: $n = 2$. Ring A shows 2, Ring B shows $(4 + 10) \bmod 12 = 2$. ✓
$x \equiv 1 \pmod 4$: candidates $1, 5, 9, 13, 17, \ldots$
Check $\bmod 5$: $1 \to 1$ ✗, $5 \to 0$ ✗, $9 \to 4$ ✗, $13 \to 3$ ✗, $17 \to 2$ ✓
So $x \equiv 17 \pmod{20}$: candidates $17, 37, 57, 77, \ldots$
Check $\bmod 7$: $17 \to 3$ ✓
Answer: $x = 17$.
Ring 1 = Ring 2: $n \equiv 3 + 4n \pmod{30}$ → $-3n \equiv 3 \pmod{30}$ → $3n \equiv 27 \pmod{30}$ → $n \equiv 9 \pmod{10}$.
Ring 1 = Ring 3: $n \equiv 5 + 7n \pmod{30}$ → $-6n \equiv 5 \pmod{30}$ → $6n \equiv 25 \pmod{30}$. But $\gcd(6,30) = 6$ and $6 \nmid 25$.
Impossible! No solution exists. 🚫
| Concept | One-liner |
|---|---|
| Modular arithmetic | Numbers that "wrap around," like a clock |
| Congruence $a \equiv b \pmod{m}$ | $a$ and $b$ have the same remainder when divided by $m$ |
| Modular equations | Algebra, but in a world that wraps around |
| GCD rule | $ax \equiv b \pmod{m}$ is solvable iff $\gcd(a,m) \mid b$ |
| Chinese Remainder Theorem | Combining multiple mod-conditions into one — works cleanly when moduli are coprime |
"In mathematics, the art of asking the right question is more important than the art of solving it." — Georg Cantor