The p-mark dial
Rotations completed
0
0
Growth part T(k)
0
0
Dial reading
0
0
Marks visited
1 / 5
1 / 5
Lesson 03 · Triangular & square remainders · 45–60 minutes
The Missing Remainders
On the 5-mark dial in Lesson 02, the pointer never landed on marks 2 and 4, no matter how long the clock turned. In this lesson you will find which marks get missed on other dials, then discover a quick test that tells you whether a mark can ever be reached, without listing the readings. Finally you will prove the test always works.
Where this lesson is headed
R(k) = T(k) mod p, T(k) = k(k − 1)2
mark a is reachable ⇔ 8a + 1 is a perfect square on the p-mark dial
In words: to find out whether the pointer can ever land on mark a, compute 8a + 1 and ask whether it is the remainder of some square number. The setup: a growing clock that starts with circumference p and grows 1 cm per rotation, read on a dial with the same p marks. As in Lesson 02, step 5, the straight part k × p is whole trips, so the reading is just T(k) mod p. We use dials whose number of marks p is an odd prime.
p: starting circumference, and the number of dial marks (an odd prime)
g = 1: growth per rotation
k: rotations completed
T(k): 0 + 1 + ⋯ + (k − 1), the extra distance from growth
a: a target mark, from 0 to p − 1
Question: can the pointer ever land on a?
01. Which marks does the pointer reach?
Start with the smallest interesting dial, p = 5. The clock starts at 5 cm and grows 1 cm per rotation. Turn it and watch which marks light up. From Lesson 02 we know an odd dial repeats every p rotations, so k = 0 to p − 1 shows everything that will ever appear. Then try bigger dials and look for a pattern. The guided experiments below walk you through it. (Shortcut: Space turns one rotation, ← undoes one.)
Guided experiments
Do these in order. "Set this up" chooses the dial and turns the clock for you.
02. Turn the question into one about squares
We want to know whether T(k) ≡ a (mod p) has a solution k. The trick is that 8T(k) + 1 is always a perfect square. Each step has the general idea on the left and the same step with your numbers on the right.
1
The question, written as a congruence
"The pointer can land on mark a" means some number of rotations k gives
T(k) ≡ a (mod p)
Checking every k works, but takes p tries. We want a test that looks only at a.
2
8T(k) + 1 is always a perfect square
Multiply T(k) by 8 and add 1:
8T(k) + 1 = 8 · k(k − 1)/2 + 1
= 4k² − 4k + 1
= (2k − 1)²
This is ordinary algebra on whole numbers, true for every k. (Multiplying by 8 clears the /2, and the result is a perfect square trinomial.)
3
Translate the question, in both directions
Forward. If T(k) ≡ a, multiply by 8 and add 1 (always allowed, Lesson 02 step 3):
(2k − 1)² ≡ 8a + 1 (mod p)
Backward. If (2k − 1)² ≡ 8a + 1, subtract 1 to get 8T(k) ≡ 8a. Now we need to cancel the 8. Lesson 02 step 4 says this is safe when 8 shares no factor with p, and p is odd, so gcd(8, p) = 1. That gives T(k) ≡ a.
T(k) ≡ a ⇔ (2k − 1)² ≡ 8a + 1
4
Every square root gives back a k
Let y = 2k − 1. Going backwards needs k from y, which means dividing by 2 on the dial. On an odd dial, "half" exists: the number h = (p + 1)/2 satisfies 2h = p + 1 ≡ 1, so multiplying by h undoes doubling.
k ≡ (y + 1) · (p + 1)/2 (mod p)
So every y on the dial comes from exactly one k in 0 to p − 1. Asking about (2k − 1)² is the same as asking about y² for any y.
5
The square test
A number is a square on the p-mark dial (a quadratic residue mod p) if it is the reading of some y², including 0. Putting steps 3 and 4 together:
mark a is reachable ⇔ 8a + 1 is a square on the p-mark dial
To use it: list the squares on the dial once (right), compute 8a + 1 mod p, and see whether it is in the list. If it is, step 4 tells you which k lands on a.
| y | y² | y² mod p |
|---|
6
Check the test on every target at once
The table compares the two methods for every mark: the square test (middle columns) and simply listing the readings (last column). They always agree.
Notice also that squares come in pairs: y and p − y have the same square, since (p − y)² = p² − 2py + y². Back in terms of k, that pairs k with p + 1 − k, which is why readings in Stage 01 came in mirror pairs and only about half the marks get reached. Lesson 04 counts them exactly.
| a | 8a + 1 mod p | Square? | Listing: reached at k = |
|---|
Challenge: recover k from a square root
Does the dial have to be prime?
No. Nothing in steps 2 to 5 used primality: 8 and 2 can be cancelled on every odd dial. Primes matter in Lesson 04, where they make the count of squares easy. Even dials need a different version of the test; see the end of Stage 03.
03. Prove the test, then find where it stops working
A proof needs both directions: reachable means 8a + 1 is a square, and 8a + 1 a square means reachable. Watch where the odd dial is used. Multiplying a congruence is always fine; cancelling is only fine when the factor shares nothing with the modulus.
Proof workshop
Complete proof · odd p ≥ 3
Forward. If T(k) ≡ a (mod p), multiply by 8 and add 1. The identity gives (2k − 1)² = 8T(k) + 1 ≡ 8a + 1, so 8a + 1 is a square mod p.
Backward. Suppose y² ≡ 8a + 1 (mod p). Since p is odd, h = (p + 1)/2 satisfies 2h ≡ 1. Choose k ≡ (y + 1)h, so 2k − 1 ≡ y. Then 8T(k) + 1 = (2k − 1)² ≡ y² ≡ 8a + 1, so 8T(k) ≡ 8a. As gcd(8, p) = 1, cancelling gives T(k) ≡ a (mod p).
Which rotations. By Lesson 02 the readings repeat every p rotations on an odd dial, so k = 0 to p − 1 covers every reading that will ever appear. ∎
Primality was never used. It becomes important in Lesson 04, for counting the squares.