AMC 10 · 2022 · #19

Grade 7 number-theory

modular-arithmeticlcmfraction-arithmetic identify-subproblemscomplementary-counting ↑ Prerequisites: modular-arithmetic

📏 Medium solution 💡 3 insights

Problem

Let L_n = lcm(1, 2, …, n). The unique integer h with

\frac{1}{1}

\frac{1}{2}

+ … +

\frac{1}{17}

\frac{h}{L₁7}

is some giant number. Find h mod 17.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

AMC 10 2022 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Identify Subproblems

Multiplying by L₁7 turns the sum into h = Σ_k=1¹⁷ $\frac{L₁7}{k}$ — a tidy sum of 17 integers. Tool #7 (Identify Subproblems) splits the question into (a) showing 16 of those 17 terms are divisible by 17 and so contribute 0 mod 17, and (b) computing the surviving single term $\frac{L₁7}{17}$ = L₁6 modulo 17. Tool #16 (Change Focus): instead of attacking h directly, count what survives mod 17 — almost everything vanishes. Tool #13 (Convert to Algebra): treat $\frac{L₁7}{k}$ symbolically and use gcd(17, k) = 1 to argue divisibility.

1STEP 1

Clear the denominators. Multiplying both sides by L₁7 gives a clean sum of integers.

h = L₁7 Σ_k=1¹⁷

\frac{1}{k}

= Σ_k=1¹⁷

\frac{L₁7}{k}

2STEP 2

Subproblem A: for k = 1…16, write L₁7 = 17 · L₁6, so each $\frac{L₁7}{k}$ = 17 · ( $\frac{L₁6}{k}$ ) is a multiple of 17.

For k ∈ {1, …, 16}:

\frac{L₁7}{k}

= 17 ·

\frac{L₁6}{k}

≡ 0 (mod 17)

3STEP 3

Subproblem B: only k = 17 survives, where $\frac{L₁7}{17}$ = L₁6, so h ≡ L₁6 (mod 17).

h ≡

\frac{L₁7}{17}

= L₁6 (mod 17)

4STEP 4

Factor L₁6 into prime powers: the highest power of each prime ≤ 16 gives 2⁴ · 3² · 5 · 7 · 11 · 13.

L₁6 = 2⁴ · 3² · 5 · 7 · 11 · 13 = 16 · 9 · 5 · 7 · 11 · 13

5STEP 5

Compute L₁6 mod 17: replace 16 ≡ -1 (mod 17) and multiply step by step, reducing mod 17 each time.

L₁6 ≡ (-1) · 9 · 5 · 7 · 11 · 13 (mod 17)

6STEP 6

Reduce after each multiply: (-1)·9≡8, then ·5≡6, ·7≡8, ·11≡3, ·13≡5, so h ≡ 5 (mod 17) → (C).

L₁6 ≡ 5 (mod 17), so h ≡ 5 (mod 17) → (C)

Answer

Independent re-check by pairing primes differently: 9 · 5 = 45 ≡ 45 - 34 = 11; 7 · 11 = 77 ≡ 77 - 68 = 9; 11 · 9 = 99 ≡ 99 - 85 = 14; multiplied by 13: 14 · 13 = 182 ≡ 182 - 170 = 12; multiplied by -1 (from the 16): 12 · (-1) = -12 ≡ 5 (mod 17). Same answer 5, choice (C). The argument that

\frac{L₁7}{k}

≡ 0 (mod 17) for k ≤ 16 is also airtight: L₁7 = 17 · L₁6 and k ∣ L₁6, so

\frac{L₁7}{k}

= 17 (

\frac{L₁6}{k}

) is an integer multiple of 17.

💡Key takeaway

Multiply both sides by L₁7 — now h is a sum of 17 integers $\frac{L₁7}{k}$ . For every k from 1 to 16, $\frac{L₁7}{k}$ is a multiple of 17 (because 17 is prime), so those 16 terms vanish mod 17. Only $\frac{L₁7}{17}$ = L₁6 = 2⁴ · 3² · 5 · 7 · 11 · 13 survives; reducing step by step mod 17 gives (C) 5.