Maths Olympiad Prep

Library / /644 of 740

Number theory Difficulty 5.5 AIME, harder Prove it United States

Problem:

Call a positive integer nn quixotic if the value of
lcm(1,2,3,,n)(11+12+13++1n) \operatorname{lcm}(1,2,3, \ldots, n) \cdot\left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}\right)
is divisible by 4545. Compute the tenth smallest quixotic integer.

Solution

Solution:

Let L=lcm(1,2,3,,n)L=\operatorname{lcm}(1,2,3, \ldots, n), and let E=L(1+12+13++1n)E=L\left(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}\right) denote the expression.

In order for nn to be quixotic, we need E0 (mod 5)E \equiv 0\ (\bmod\ 5) and E0 (mod 9)E \equiv 0\ (\bmod\ 9). We consider these two conditions separately.

Claim: E0 (mod 5)E \equiv 0\ (\bmod\ 5) if and only if n[45k,5k+1)n \in\left[4 \cdot 5^{k}, 5^{k+1}\right) for some nonnegative integer kk.

Proof. Let k=log5nk=\left\lfloor\log _{5} n\right\rfloor, which is equal to ν5(L)\nu_{5}(L). In order for EE to be divisible by 55, all terms in L1,L2,,Ln\frac{L}{1}, \frac{L}{2}, \ldots, \frac{L}{n} that aren't multiples of 55 must sum to a multiple of 55. The potential terms that are not going to be multiples of 55 are L/5k,L/(25k),L/(35k)L / 5^{k}, L /(2 \cdot 5^{k}), L /(3 \cdot 5^{k}), and L/(45k)L /(4 \cdot 5^{k}), depending on the value of nn.

- If n[5k,25k)n \in\left[5^{k}, 2 \cdot 5^{k}\right), then only L/5kL / 5^{k} appears. Thus, the sum is L/5kL / 5^{k}, which is not a multiple of 55.
- If n[25k,35k)n \in\left[2 \cdot 5^{k}, 3 \cdot 5^{k}\right), then only L/5kL / 5^{k} and L/(25k)L /(2 \cdot 5^{k}) appear. The sum is 3L/(25k)3 L /(2 \cdot 5^{k}), which is not a multiple of 55.
- If n[35k,45k)n \in\left[3 \cdot 5^{k}, 4 \cdot 5^{k}\right), then only L/5k,L/(25k)L / 5^{k}, L /(2 \cdot 5^{k}), and L/(35k)L /(3 \cdot 5^{k}) appear. The sum is 11L/(65k)11 L /(6 \cdot 5^{k}), which is not a multiple of 55.
- If n[45k,5k+1)n \in\left[4 \cdot 5^{k}, 5^{k+1}\right), then L/5k,L/(25k),L/(35k)L / 5^{k}, L /(2 \cdot 5^{k}), L /(3 \cdot 5^{k}), and L/(45k)L /(4 \cdot 5^{k}) all appear. The sum is 25L/(125k)25 L /(12 \cdot 5^{k}), which is a multiple of 55. Thus, this case works.

Only the last case works, implying the claim.

Claim: E0 (mod 9)E \equiv 0\ (\bmod\ 9) if and only if n[73k1,83k1)n \in\left[7 \cdot 3^{k-1}, 8 \cdot 3^{k-1}\right) for some positive integer kk.

Proof. This is a repeat of the previous proof, so we will only sketch it. Let k=log3nk=\left\lfloor\log _{3} n\right\rfloor, which is equal to ν3(L)\nu_{3}(L). This time, the terms we need to consider are those that are not multiples of 99, which are
L3k1,L23k1,,L83k1 \frac{L}{3^{k-1}}, \frac{L}{2 \cdot 3^{k-1}}, \cdots, \frac{L}{8 \cdot 3^{k-1}}
Similar to the above, we need to check that the sum of the first jj terms is divisible by 99 if and only if j=7j=7. There are 88 cases, but we could reduce workload by showing first that it is divisible by 33 if and only if j{6,7,8}j \in\{6,7,8\} (there are only L/3kL / 3^{k} and L/(23k)L /(2 \cdot 3^{k}) to consider), then eliminate 66 and 88 by using (mod 9)(\bmod\ 9).

Doing a little bit of arithmetic, we'll get the first 1010 quixotic numbers: 21,22,23,567,568,569,570,571,572,57321, 22, 23, 567, 568, 569, 570, 571, 572, 573.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.