Competition · AMC preparation · step 4 of 4

AMC 10 · 2022A · #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₁₇}

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₁₇ turns the sum into h = Σ_k=1¹⁷ L₁₇/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 L₁₇/17 = L₁₆ 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 L₁₇/k symbolically and use gcd(17, k) = 1 to argue divisibility.

1STEP 1

Clear the denominators

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

h = L₁₇ Σ_k=1¹⁷ 1/k = Σ_k=1¹⁷ L₁₇/k

2STEP 2

Show most terms vanish

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

For k ∈ {1, …, 16}: L₁₇/k = 17 · L₁₆/k ≡ 0 (mod 17)

3STEP 3

Keep the surviving term

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

h ≡ L₁₇/17 = L₁₆ (mod 17)

4STEP 4

Factor into prime powers

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

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

5STEP 5

Reduce each factor mod 17

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

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

6STEP 6

Multiply the remainders

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

L₁₆ ≡ 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₁₇}{k}

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

\frac{L₁₇}{k}

= 17 (

\frac{L₁₆}{k}

) is an integer multiple of 17.

💡Key takeaway

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

Clear the denominators
Show most terms vanish
Keep the surviving term
Factor into prime powers
Reduce each factor mod 17
Multiply the remainders

A parent dashboard for the family lives at sensimlab.com.