🔢 The Ring Puzzle

Math Circle Lecture Plan  |  Ages 11–12  |  Duration: 90 minutes (with break)  |  Topic: Modular Arithmetic & the Chinese Remainder Theorem


Part 0 — Warm-Up: Clock Arithmetic (10 min)

The Big Idea

"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."

Quick Practice (hands up — shout it out!)

QuestionAnswer
$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$

Key Rule — The Remainder Rule

When we do $a \bmod m$, we keep subtracting $m$ until we get a number from $0$ to $m - 1$.

That set of numbers $\{0, 1, 2, \ldots, m-1\}$ is our "world." Everything wraps around and lives in that world. A clock is the world $\{0, 1, 2, \ldots, 11\}$.

Part 1 — The Two-Ring Puzzle (20 min)

Setting the Scene

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?

Let's Build a Table Together

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?
001✗
114✗
227✗
330✗
443✗
556✗
669✗
772✗
885✗
998✗
1001✗

Hmm! After 10 presses we're back to the start. It seems like it never matches!

But Why? Let's Use Algebra

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!

Lesson: Some puzzles have no solution. Whether a solution exists depends on the relationship between the step sizes and the ring size.

What If We Change the Start?

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$

Answer: $n = 5$. Ring A shows $5$, Ring B shows $(3 \times 5) \bmod 10 = 15 \bmod 10 = 5$. ✓

Discussion prompt: "Why did changing the starting position from 1 to 0 suddenly make it solvable?"


Part 2 — The Three-Ring Puzzle ⭐ (25 min)

The Real Challenge

Now we have three rings, each with numbers 0 to 25 (26 positions). One button — all three move at once:

RingStarts atSteps per press
101
212
323

After $n$ presses:

RingShows
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?

Step-by-Step: Compare Them in Pairs

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.

Equation 1: Ring 1 = Ring 2

$$n \equiv 1 + 2n \pmod{26}$$

Subtract $2n$ from both sides:

$$-n \equiv 1 \pmod{26}$$

Multiply both sides by $-1$:

$$n \equiv -1 \equiv 25 \pmod{26}$$
Ring 1 and Ring 2 match when: $n = 25, 51, 77, 103, \ldots$

Equation 2: Ring 1 = Ring 3

$$n \equiv 2 + 3n \pmod{26}$$ $$-2n \equiv 2 \pmod{26}$$ $$2n \equiv -2 \equiv 24 \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}$$
Ring 1 and Ring 3 match when: $n = 12, 25, 38, 51, \ldots$

Can We Satisfy Both at Once?

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.

$n = 25$ presses. All rings show 25.

Verify together on the board:

🧠 Intuition Corner

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.


☕
Break — 5 minutes

Part 3 — Introduction to Modular Equations (10 min)

Solving Equations in Mod-World

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. ✓

When Can We Divide?

Try: $2x \equiv 3 \pmod{6}$

Left side is always even, right side is odd. No solution!

$ax \equiv b \pmod{m}$ has a solution only when $\gcd(a, m)$ divides $b$.

Where $\gcd$ is the greatest common divisor — the biggest number that divides both $a$ and $m$.

Mini-Exercise (pair work)

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$)

Part 4 — The Chinese Remainder Theorem 🏯 (20 min)

For the advanced/curious kids. This is the "boss level."

A Story From Ancient China

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}$$

Solving It By Sieving

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$?

Answer: $x \equiv 23 \pmod{105}$ (where $105 = 3 \times 5 \times 7$).

The farmer has 23 eggs (or 128, or 233, …).

The Chinese Remainder Theorem — Statement

If the moduli are pairwise coprime (share no common factors), then the system of congruences has exactly one solution modulo the product of all moduli.

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$.

When It Breaks Down

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!)

No overlap ever. No solution exists!

Connection to Our Ring Puzzle

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$.


Part 5 — Challenge Problems 🧩 (take-home)

BRONZE

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.

SILVER

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.

GOLD

Three rings, 0–29 (30 positions).

RingStartStep
101
234
357

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!


Answer Key (for instructors)

Bronze Solution

$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$. ✓

Silver Solution

$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$.

Gold Solution

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. 🚫


Summary — What We Learned Today

ConceptOne-liner
Modular arithmeticNumbers that "wrap around," like a clock
Congruence $a \equiv b \pmod{m}$$a$ and $b$ have the same remainder when divided by $m$
Modular equationsAlgebra, but in a world that wraps around
GCD rule$ax \equiv b \pmod{m}$ is solvable iff $\gcd(a,m) \mid b$
Chinese Remainder TheoremCombining 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