Skip to main content

2022 AMC 12A Problem 23

Problem 23 of 25HarderNumber Theory

Let hnh_n and knk_n be the unique relatively prime positive integers such that 11+12+13++1n=hnkn.\frac11+\frac12+\frac13+\cdots+\frac1n=\frac{h_n}{k_n}. Let LnL_n denote the least common multiple of the numbers 1,1, 2,2, 3,3, ,\ldots, n.n. For how many integers nn with 1n221\le n\le22 is kn<Ln?k_n\lt L_n?

Answer choices

Show solution

Solution

LnL_n is always divisible by kn,k_n, so kn<Lnk_n\lt L_n exactly when some prime pp divides both LnL_n and the numerator N=k=1nLnkN=\sum_{k=1}^n \tfrac{L_n}{k} (i.e. a prime cancels). For a prime pp with maximal power pan,p^a\le n, only the terms with vp(k)=av_p(k)=a keep pp out of Lnk;\frac{L_n}{k}; all others are divisible by p.p. So pp cancels iff vp(k)=aLnk0(modp).\sum_{v_p(k)=a}\tfrac{L_n}{k}\equiv0\pmod p. Applying this test recursively with Hn=Hn1+1nH_n=H_{n-1}+\frac{1}{n} gives kn=Lnk_n=L_n for 1n5,1\le n\le5, kn=Ln3k_n=\frac{L_n}{3} for 6n8,6\le n\le8, and kn=Lnk_n=L_n again for 9n17.9\le n\le17. Finally, the ratios Lnkn\frac{L_n}{k_n} for n=18,19,20,21,22n=18,19,20,21,22 are 3,3,15,45,45,3,3,15,45,45, respectively. Thus cancellation occurs precisely for n=6,7,8,18,19,20,21,22,n=6,7,8,18,19,20,21,22, which is 88 values. Thus, the correct answer is D.

More practice

Concepts: least common multiple · prime factorization · modular arithmetic

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