AMC 10 · 2022 · #19

Grade 7 number-theory

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

📏 Medium solution 💡 3 insights

Problem

Define $L_n$ as the least common multiple of all the integers from $1$ to $n$ inclusive. There is a unique integer $h$ such that
$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{17}=\frac{h}{L_{17}}$
What is the remainder when $h$ is divided by $17$ ?

$\textbf{(A) } 1 \qquad \textbf{(B) } 3 \qquad \textbf{(C) } 5 \qquad \textbf{(D) } 7 \qquad \textbf{(E) } 9$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: Let $L_n = \operatorname{lcm}(1, 2, \dots, n)$. The unique integer $h$ with $\tfrac{1}{1} + \tfrac{1}{2} + \dots + \tfrac{1}{17} = \tfrac{h}{L_{17}}$ is some giant number. Find $h \bmod 17$.

Givens: $L_{17} = \operatorname{lcm}(1, 2, \dots, 17)$; $\dfrac{1}{1} + \dfrac{1}{2} + \dots + \dfrac{1}{17} = \dfrac{h}{L_{17}}$; Choices: (A) $1$, (B) $3$, (C) $5$, (D) $7$, (E) $9$

Unknowns: $h \bmod 17$

Understand

Givens: $L_{17} = \operatorname{lcm}(1, 2, \dots, 17)$; $\dfrac{1}{1} + \dfrac{1}{2} + \dots + \dfrac{1}{17} = \dfrac{h}{L_{17}}$; Choices: (A) $1$, (B) $3$, (C) $5$, (D) $7$, (E) $9$

Plan

Primary tool: #7 Identify Subproblems

Secondary: #16 Change Focus / Complement, #13 Convert to Algebra

Multiplying by $L_{17}$ turns the sum into $h = \sum_{k=1}^{17} L_{17}/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}/17 = L_{16}$ 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_{17}/k$ symbolically and use $\gcd(17, k) = 1$ to argue divisibility.

Execute — Answer: C

#13 Convert to Algebra 6.NS.A.1 Step 1

Clear the denominators.
Multiplying both sides by $L_{17}$ gives a clean sum of integers.

$$h = L_{17} \sum_{k=1}^{17} \dfrac{1}{k} = \sum_{k=1}^{17} \dfrac{L_{17}}{k}$$

💡 $L_{17}/k$ is an integer because $L_{17}$ is built to be divisible by every $k \le 17$.

#7 Identify Subproblems 6.NS.B.4 Step 2

Subproblem A: show that for $k = 1, 2, \dots, 16$ the term $L_{17}/k$ is a multiple of $17$.
Since $17$ is prime and $1 \le k \le 16$, $\gcd(17, k) = 1$.
Write $L_{17} = 17 \cdot L_{16}$ (because $\operatorname{lcm}(L_{16}, 17) = 17 \cdot L_{16}$ when $\gcd(L_{16}, 17) = 1$).
Then $L_{17}/k = 17 \cdot (L_{16}/k)$, and since $k$ divides $L_{16}$ (every $k \le 16$ divides $L_{16}$), $L_{16}/k$ is an integer.
So $L_{17}/k$ is $17 \cdot \text{integer}$.

For $k \in \{1, \dots, 16\}: \quad \dfrac{L_{17}}{k} = 17 \cdot \dfrac{L_{16}}{k} \equiv 0 \pmod{17}$

💡 The factor of $17$ inside $L_{17}$ stays put when you divide by anything coprime to $17$.

#16 Change Focus / Complement 6.NS.B.4 Step 3

Subproblem B: the only surviving term is $k = 17$, where $L_{17}/17 = L_{16}$.
So modulo $17$, $h \equiv L_{16}$.

$$h \equiv \dfrac{L_{17}}{17} = L_{16} \pmod{17}$$

💡 Sixteen terms vanish mod $17$; only one is left, and that one equals $L_{16}$.

#7 Identify Subproblems 6.NS.B.4 Step 4

Factor $L_{16}$ using prime-power factorization: take the highest power of each prime that is at most $16$.
Primes up to $16$: $2, 3, 5, 7, 11, 13$.
Highest powers: $2^4 = 16$, $3^2 = 9$, $5, 7, 11, 13$.

$$L_{16} = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 16 \cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13$$

💡 LCM of $1, \dots, 16$ is built by taking the strongest copy of each prime $\le 16$.

#13 Convert to Algebra 7.NS.A.2 Step 5

Compute $L_{16} \bmod 17$.
Replace $16 \equiv -1 \pmod{17}$ and multiply step by step, reducing mod $17$ each time.

$$L_{16} \equiv (-1) \cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \pmod{17}$$

💡 Use the trick $16 \equiv -1$ to keep numbers small and signs trackable.

#13 Convert to Algebra 7.NS.A.2 Step 6

Carry out the step-by-step reduction.
$(-1) \cdot 9 = -9 \equiv 8$.
$8 \cdot 5 = 40 \equiv 40 - 34 = 6$.
$6 \cdot 7 = 42 \equiv 42 - 34 = 8$.
$8 \cdot 11 = 88 \equiv 88 - 85 = 3$.
$3 \cdot 13 = 39 \equiv 39 - 34 = 5$.

$L_{16} \equiv 5 \pmod{17}$, so $h \equiv 5 \pmod{17} \;\Rightarrow\; \textbf{(C)}$

💡 Reduce after every multiply — keeps every intermediate at most two-digit.

[1] #13 6.NS.A.1 Clear the denominators. Multiplying both sides by $L_{17}$ gives a clean sum of

[2] #7 6.NS.B.4 Subproblem A: show that for $k = 1, 2, \dots, 16$ the term $L_{17}/k$ is a multi

[3] #16 6.NS.B.4 Subproblem B: the only surviving term is $k = 17$, where $L_{17}/17 = L_{16}$. S

[4] #7 6.NS.B.4 Factor $L_{16}$ using prime-power factorization: take the highest power of each

[5] #13 7.NS.A.2 Compute $L_{16} \bmod 17$. Replace $16 \equiv -1 \pmod{17}$ and multiply step by

[6] #13 7.NS.A.2 Carry out the step-by-step reduction. $(-1) \cdot 9 = -9 \equiv 8$. $8 \cdot 5 =

Review

Reasonableness: Independent re-check by pairing primes differently: $9 \cdot 5 = 45 \equiv 45 - 34 = 11$; $7 \cdot 11 = 77 \equiv 77 - 68 = 9$; $11 \cdot 9 = 99 \equiv 99 - 85 = 14$; multiplied by $13$: $14 \cdot 13 = 182 \equiv 182 - 170 = 12$; multiplied by $-1$ (from the $16$): $12 \cdot (-1) = -12 \equiv 5 \pmod{17}$. Same answer $5$, choice (C). The argument that $L_{17}/k \equiv 0 \pmod{17}$ for $k \le 16$ is also airtight: $L_{17} = 17 \cdot L_{16}$ and $k \mid L_{16}$, so $L_{17}/k = 17 (L_{16}/k)$ is an integer multiple of $17$.

Alternative: Tool #5 (Look for a Pattern) via Wolstenholme-style symmetry: pair fractions $\tfrac{1}{k} + \tfrac{1}{17-k}$ for $k = 1, \dots, 8$. Each pair sums to $\tfrac{17}{k(17-k)}$. Multiplied by $L_{17}$, each becomes $\tfrac{17 \cdot L_{17}}{k(17-k)}$, which is $17 \cdot (\text{integer})$ — so all 16 paired terms vanish mod $17$, leaving just $L_{17}/17 = L_{16}$. Same conclusion in fewer divisibility checks.

CCSS standards used (min grade 7)

6.NS.A.1 Interpret and compute quotients of fractions and solve word problems (Clearing the denominator on the harmonic sum: multiplying through by $L_{17}$ to turn the equation into $h = \sum L_{17}/k$.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Working with $L_{17} = \operatorname{lcm}(1, \dots, 17) = 17 \cdot L_{16}$ and reading off prime-power components of $L_{16}$.)
7.NS.A.2 Apply and extend understanding of multiplication and division of rational numbers (Computing $L_{16} \bmod 17 = (-1) \cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \bmod 17$ by reducing after each step.)

⭐ Multiply both sides by $L_{17}$ — now $h$ is a sum of $17$ integers $L_{17}/k$. For every $k$ from $1$ to $16$, $L_{17}/k$ is a multiple of $17$ (because $17$ is prime), so those $16$ terms vanish mod $17$. Only $L_{17}/17 = L_{16} = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13$ survives; reducing step by step mod $17$ gives $\textbf{(C) }5$.