2022 AMC 10A Problem 19

Problem 19 of 25HarderNumber Theory

Let

L_n

denote the least common multiple of the numbers

1,

2,

3,

\ldots,

n,

and let

h

be the unique positive integer such that

\dfrac{1}{1} + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{17} = \dfrac{h}{L_{17}}

What is the remainder when

h

is divided by

17?

Show solution

Solution

Multiplying the harmonic sum by

L_{17},

we get

h=\sum_{i=1}^{17}\frac{L_{17}}{i}.

For

1\le i\le16,

the term

\frac{L_{17}}{i}

is still divisible by

17,

so these terms contribute

0\pmod{17}.

Thus

h\equiv \frac{L_{17}}{17}\pmod{17}.

The least common multiple

L_{17}

contains the prime-power factors

16,9,5,7,11,13,17,

so

\begin{aligned} \frac{L_{17}}{17} &\equiv 16\cdot9\cdot5\cdot7\cdot11\cdot13 \\ &\pmod{17}. \end{aligned}

Reducing modulo

17,

this is

(-1)\cdot9\cdot5\cdot7\cdot11\cdot13

\equiv5\pmod{17}.

Thus, C is the correct answer.

More practice

Concepts: modular arithmetic · least common multiple · prime factorization

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.