The m-mark dial
Reached in 1st block1
Reached so far1
Added by 2nd block0
Lesson 07 · Factorization · 55–65 minutes
Composite Dials & Prime Factorization
Lesson 06 reduced every count to B(m), the number of marks the 1st block reaches on an m-mark dial. But so far B(m) has meant listing readings. Here you will compute it straight from the prime factorization of m. The key idea: one big dial behaves like several small dials read at the same time. Along the way you will finally prove the no-bonus lemma that Lesson 06 borrowed.
Where this lesson is headed
B(m) = 2a · ∏ Q(pe) − δ(m)
In words: split the dial into its prime-power pieces, count each piece, multiply, and subtract 1 only for a pure power of two. Write m = 2a × (odd part); the product runs over the odd prime powers pe in the odd part (an empty product is 1). Same setup as Lessons 03 to 05: a clock starting at circumference m, growing 1 cm per rotation, on an m-mark dial, so the reading is T(k) mod m.
B(m): marks reached in the 1st block, k = 0 to m − 1 (Lesson 06)
F(m): marks ever reached (two blocks, k = 0 to 2m − 1, are enough by Lesson 02)
Q(pe): number of squares on a pe-mark dial, p an odd prime
δ(m): 1 when m is 2, 4, 8, …; 0 otherwise
01. A 6-mark dial is a 2-mark dial and a 3-mark dial at once
Start with the simplest composite dial, 6 = 2 × 3. Any mark on the 6-mark dial can be described by two small readings: what it reads on a 2-mark dial and on a 3-mark dial. The grid on the right shows every mark by its pair of small readings. Turn the clock and watch both. (Shortcut: Space turns one rotation, ← undoes one.)
Settings
Dial size m
The pair grid
Reached so farReached laterNever reached
Tap a cell to see how its mark is rebuilt from the two small readings.
Guided experiments
Do these in order. "Set this up" chooses the dial and turns the clock for you.
Rotation by rotation
| k | T(k) | mod u | mod v | Reading | New? |
|---|
A tempting guess
We can count marks on each small dial. Which product gives the count on the big dial?
02. Split the dial, count the pieces, multiply
Each step has the general idea on the left and your numbers on the right. Steps 1 and 2 use your dial from Stage 01; steps 4 and 5 have their own inputs.
1
A mark is the same as a pair of small readings
Let m = u × v where u and v share no factor. Every mark x on the m-mark dial gives a pair (x mod u, x mod v), and every pair comes from exactly one mark. This is the Chinese Remainder Theorem (CRT).
Every pair is used. To get x ≡ a (mod u) and x ≡ b (mod v), try x = a + u·t. We need u·t ≡ b − a (mod v). Since u shares no factor with v, u can be undone on the v-mark dial (Lesson 02, step 4), so a suitable t exists.
No pair is used twice. If two marks give the same pair, their difference is a multiple of u and of v, so of uv = m. On the m-mark dial they are the same mark.
Try it
Find the mark x from 0 to 44 with x ≡ 3 (mod 9) and x ≡ 2 (mod 5).
2
All-marks counts multiply
Pick any mark A reachable on the u-dial and any mark B reachable on the v-dial. Is there one rotation k that gives both at once?
On an odd dial the readings repeat every u rotations, and on a power-of-two dial every 2u (Lesson 02). So "reading A" is a condition on k mod u (or mod 2u), and "reading B" is a condition on k mod v. Those rotation counts share no factor either, so CRT again gives one k satisfying both.
F(uv) = F(u) × F(v)
This is about all marks ever reached. The 1st block alone need not contain the k that CRT produces, which is why B does not multiply.
3
Count each piece
Power of two, 2a: the two blocks together hit every mark (Lesson 05), so F(2a) = 2a.
Odd prime power, pe: by Lesson 03, 8T(k) + 1 = (2k − 1)², and on any odd dial both k ↦ 2k − 1 and r ↦ 8r + 1 can be undone. So the marks T reaches correspond one to one with the squares on the dial: F(pe) = Q(pe).
For e = 1 this is (p + 1)/2 (Lesson 04). For higher powers, step 4 counts them.
4
Squares on a pe-mark dial
A nonzero square on a pe-mark dial has the form p2j × w, where w is a square that shares no factor with p, and 2j < e. Sort squares by j into layers and count each layer.
In layer j, w is a "unit square" on a pe−2j-mark dial. There are φ(ps) = ps − ps−1 units on a ps-dial, and each unit square has exactly two roots, y and −y (the Lesson 04 argument: y² ≡ z² gives (y − z)(y + z) ≡ 0, and p cannot divide both factors). So each layer has φ/2 squares. Add 1 for the square 0:
Q(pe) = 1 + ∑j = 0 … ⌊(e − 1)/2⌋ φ(pe−2j)/2
Do not reuse (p + 1)/2 for a prime power: on 9 marks it would give 5, but only 4 marks are squares.
| Layer | Divisible by | Unit dial | Count | Squares in it |
|---|
Dial pe9
Formula Q4
Listed squares4
5
Put it together
Split m = 2a × p1e1 × p2e2 × ⋯. The pieces share no factors, so steps 2 and 3 give
F(m) = 2a × Q(p1e1) × Q(p2e2) × ⋯
Then the 1st block: on an odd dial it repeats forever, so B = F. On a pure power of two it misses exactly m/2 (Lesson 05), so B = F − 1. On any other even dial it misses nothing (the no-bonus lemma, proved in Stage 03), so B = F.
B(m) = F(m) − δ(m)
| Step | Value | Why |
|---|
Formula F(m)
Formula B(m)
Listed B(m)
03. Prove the formula, and pay off Lesson 06
The formula rests on CRT, the square count, Lesson 05, and the no-bonus lemma. First check the logic of the formula. Then use CRT to prove the no-bonus lemma itself.
The claim
m = 2ab with b odd ⟹ B(m) = 2a ∏pe ∥ b Q(pe) − δ(m)
pe ∥ b means pe is the highest power of p dividing b.
Complete proof
- Odd prime powers. 8T(k) + 1 = (2k − 1)², and on an odd dial both maps can be undone, so T reaches exactly as many marks on a pe-dial as there are squares. Sorting nonzero squares by the power of p they contain gives Q(pe) = 1 + ∑ φ(pe−2j)/2.
- The power-of-two piece. By Lesson 05, rotations k = 0 to 2a+1 − 1 reach every mark of a 2a-dial, so F(2a) = 2a (and F(1) = 1).
- CRT for all marks. Write m = 2a ∏ pe. A reading on each odd piece is a condition on k mod pe; a reading on the 2a piece is a condition on k mod 2a+1. These moduli share no factors, so CRT gives one k meeting all conditions. Hence F(m) = 2a ∏ Q(pe).
- The 1st block. Odd m: readings repeat every m rotations, so B = F. m = 2a with a ≥ 1: B = F − 1 by Lesson 05. Other even m: B = F by the no-bonus lemma, proved below. ∎
Paying off Lesson 06
Proof of the no-bonus lemma
Claim: if m is even but not a power of two, the 1st block already reaches every mark the clock will ever reach. We prove it in two moves.
1
Mirror pairs: the 2nd block can only add m/2
T(1 − k) = (1 − k)(−k)/2 = k(k − 1)/2 = T(k) exactly: the mirror pairs from Lessons 03 and 04. Readings repeat every 2m rotations, so rotation 2m + 1 − k reads the same as k.
For k from m + 2 to 2m − 1, the partner 2m + 1 − k runs from m − 1 down to 2, inside the 1st block. So the only 2nd-block rotations that could add something new are k = m and k = m + 1. Both read
T(m) ≡ T(m + 1) ≡ m/2 (mod m)
So the 2nd block adds a mark only if m/2 is missing from the 1st block.
2
CRT finds m/2 inside the 1st block
Write m = 2rs with s odd, s > 1. We want k with T(k) ≡ m/2. Split the dial into its 2r piece and its s piece:
s piece: m/2 reads 0, and T(k) reads 0 whenever k ≡ 0 or 1 (mod s).
2r piece: m/2 reads 2r−1, the halfway mark, which Lesson 05 says is reached exactly when k ≡ 2r or 2r + 1 (mod 2r+1).
CRT gives one k (from 0 to 2m − 1) for each of the four combinations. Two of them are k = m and m + 1. The other two are a mirror pair k₀ and 2m + 1 − k₀, which are different from m and m + 1 because s > 1. One of a mirror pair always lies in the 1st block. So m/2 is reached in the 1st block, and by move 1 the 2nd block adds nothing. ∎
When s = 1 (a power of two) the four combinations collapse to just m and m + 1, which is exactly why powers of two get the bonus.
One counterexample is enough
"B(uv) = B(u) × B(v)" is false, and a single example proves it:
B(6) = 4 ≠ 1 × 2 = B(2) × B(3)
But F(6) = 4 = 2 × 2 = F(2) × F(3). The 2-mark dial's 1st block misses mark 1, and that missed mark is found again once all marks are counted.
Extension
Explain why multiplying 1st-block counts also fails for 72 = 8 × 9: it gives B(8) × B(9) = 7 × 4 = 28, while the correct answer is 8 × 4 = 32.
Computer check
For every dial from 1 to 360, compares the formula with listing readings directly (both F and B). Also checks the square count for odd prime powers up to 2,000 and the no-bonus lemma for every even dial up to 360.
Not run yet. Many matches are strong evidence, but only the proof covers every dial.
Exit problem · use the method
1. Find B(180) from the factorization of 180. 2. Use Lesson 06 to find C(96, 3), the marks a clock with N = 96 and g = 3 reaches on a 96-mark dial.