AMC12 2022 A

AMC12 2022 A · Q23

AMC12 2022 A · Q23. It mainly tests GCD & LCM, Number theory misc.

Let $h_n$ and $k_n$ be the unique relatively prime positive integers such that \[\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=\frac{h_n}{k_n}.\] Let $L_n$ denote the least common multiple of the numbers $1, 2, 3, \ldots, n$. For how many integers with $1\le{n}\le{22}$ is $k_n<L_n$?

设 $h_n$ 和 $k_n$ 是唯一互质的正整数使得 \[\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=\frac{h_n}{k_n}.\] 设 $L_n$ 表示 $1, 2, 3, \ldots, n$ 的最小公倍数。有多少个整数满足 $1\le{n}\le{22}$ 且 $k_n<L_n$？

(A) 0 0

(B) 3 3

(D) 8 8

(E) 10 10

Answer

Correct choice: (D)

正确答案：（D）

Solution

We are given that \[\sum_{i=1}^{n}\frac1i = \frac{1}{L_n}\sum_{i=1}^{n}\frac{L_n}{i} = \frac{h_n}{k_n}.\] Since $k_n < L_n,$ we need $\gcd\left(\sum_{i=1}^{n}\frac{L_n}{i}, L_n\right)>1.$ For all primes $p$ such that $p\leq n,$ let $\nu_p(L_n)=e\geq1$ be the exponent of the largest power of $p$ that divides $L_n.$ It is clear that $L_n\equiv0\pmod{p},$ so we test whether $\sum_{i=1}^{n}\frac{L_n}{i}\equiv0\pmod{p}.$ Note that \[\sum_{i=1}^{n}\frac{L_n}{i} \equiv \sum_{i=1}^{\left\lfloor\tfrac{n}{p^e}\right\rfloor}\frac{L_n}{ip^e} \ (\operatorname{mod} \ p^e) \equiv \sum_{i=1}^{\left\lfloor\tfrac{n}{p^e}\right\rfloor}\frac{L_n}{ip^e} \ (\operatorname{mod} \ p).\] We construct the following table for $\nu_p(L_n)=e:$ Note that: 1. If the Sum column has only one term, then it is never congruent to $0$ modulo $p.$ 2. If $p$ and $q$ are positive integers such that $p\geq q,$ then $L_p$ is a multiple of $L_q.$ Therefore, for a specific case, if the sum is congruent to $0$ modulo $p$ for the smallest element in the interval of $n,$ then it is also congruent to $0$ modulo $p$ for all other elements in the interval of $n.$ Together, there are $\boxed{\textbf{(D) }8}$ such integers $n,$ namely \[6,7,8,18,19,20,21,22.\]

给定 \[\sum_{i=1}^{n}\frac1i = \frac{1}{L_n}\sum_{i=1}^{n}\frac{L_n}{i} = \frac{h_n}{k_n}.\] 因为 $k_n < L_n$，我们需要 $\gcd\left(\sum_{i=1}^{n}\frac{L_n}{i}, L_n\right)>1$。对于所有素数 $p$ 使得 $p\leq n$，设 $\nu_p(L_n)=e\geq1$ 是 $p$ 的最高幂的指数，该幂除 $L_n$。显然 $L_n\equiv0\pmod{p}$，所以我们检验 $\sum_{i=1}^{n}\frac{L_n}{i}\equiv0\pmod{p}$。注意 \[\sum_{i=1}^{n}\frac{L_n}{i} \equiv \sum_{i=1}^{\left\lfloor\tfrac{n}{p^e}\right\rfloor}\frac{L_n}{ip^e} \ (\operatorname{mod} \ p^e) \equiv \sum_{i=1}^{\left\lfloor\tfrac{n}{p^e}\right\rfloor}\frac{L_n}{ip^e} \ (\operatorname{mod} \ p).\] 我们为 $\nu_p(L_n)=e$ 构造以下表格：注意： 1. 如果 Sum 列只有一个项，则它永不全同余 $0$ 模 $p$。 2. 如果 $p$ 和 $q$ 是正整数使得 $p\geq q$，则 $L_p$ 是 $L_q$ 的倍数。因此，对于特定情况，如果和对于区间中 $n$ 的最小元素全同余 $0$ 模 $p$，则对于区间中所有其他元素也全同余 $0$ 模 $p$。总共，有 $\boxed{\textbf{(D) }8}$ 个这样的整数 $n$，即 \[6,7,8,18,19,20,21,22.\]

Topics