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 1≤n≤221\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 pa≤n,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)=aLnk≡0(modp).\sum_{v_p(k)=a}\tfrac{L_n}{k}\equiv0\pmod p. Applying this test recursively with Hn=Hn−1+1nH_n=H_{n-1}+\frac{1}{n} gives kn=Lnk_n=L_n for 1≤n≤5,1\le n\le5, kn=Ln3k_n=\frac{L_n}{3} for 6≤n≤8,6\le n\le8, and kn=Lnk_n=L_n again for 9≤n≤17.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.
AoPS wiki

Tagged: least common multiple · prime factorization · modular arithmetic

More practice