2021 AIME I 第 14 题

先试着解答 2021 AIME I 第 14 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2021 AIME I 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

14.

对任意正整数 aaσ(a)\sigma(a) 表示 aa 的所有正整数因数之和。设 nn 是使 σ(an)1\sigma(a^n) - 1 能被 20212021 整除的最小正整数,其中该条件须对所有正整数 aa 成立。求 nn 的质因数分解中所有质因数的和。

For any positive integer a,a, σ(a)\sigma(a) denotes the sum of the positive integer divisors of a.a. Let nn be the least positive integer such that σ(an)1\sigma(a^n) - 1 is divisible by 20212021 for all positive integers a.a. Find the sum of the prime factors in the prime factorization of n.n.

答案:125
知识点:因数之和乘法阶最小公倍数模运算
难度评级:3270
小提示:

分解 2021=43472021 = 43 \cdot 47。由于 σ\sigma 是乘法函数,只需保证 p+p2++pen0p + p^2 + \cdots + p^{en} \equiv 0 在模 4343 和模 4747 下都成立,其中 pp 是任意质数,ee 是任意正整数

Factor 2021=4347.2021 = 43 \cdot 47. Since σ\sigma is multiplicative, it suffices to force p+p2++pen0p + p^2 + \cdots + p^{en} \equiv 0 modulo 4343 and 4747 for every prime pp and every positive integer ee

大提示:

满足 p1(modq)p \equiv 1 \pmod q 的质数会迫使 qq 整除 nn,而模 qq 的原根质数会迫使 q1q - 1 整除 nn;取最小公倍数

Primes p1(modq)p \equiv 1 \pmod q force qq to divide n,n, while primes that are primitive roots mod qq force q1q - 1 to divide n;n; take the least common multiple

解答:

注意 2021=43472021 = 43 \cdot 47。若 a=pieia = \prod p_i^{e_i},则 σ(an)=σ(piein)\sigma(a^n) = \prod \sigma(p_i^{e_i n}),所以只需(且取 aa 为质数可知也必须)有 σ(pN)1\sigma(p^N) \equiv 1,即 p+p2++pN0p + p^2 + \cdots + p^N \equiv 0 (mod4347)\pmod{43 \cdot 47},其中 pp 是任意质数,NNnn 的任意倍数。

固定 q{43,47}q \in \{43, 47\}。若 qq 整除 pp,则和为 00。若 p1(modq)p \equiv 1 \pmod q,则该和 N\equiv N,所以选择这样的质数(由狄利克雷定理)会迫使 qq 整除 nn。否则,和为 ppN1p1p \cdot \frac{p^N - 1}{p - 1},其中 p1p - 1 可逆,所以需要 pN1(modq)p^N \equiv 1 \pmod q;选择 pp 为模 qq 的一个原根质数会迫使 q1q - 1 整除 nn。反过来,如果 q(q1)q(q-1) 整除 nn,那么对每个 NN,只要它是 nn 的倍数,并且对每个质数 pp,该和在上述三种情形中都模 qq 为零。因此最小的 nnn=lcm(4342, 4746)=237234347 \begin{aligned} n &= \operatorname{lcm}(43 \cdot 42,\ 47 \cdot 46) \\ &= 2 \cdot 3 \cdot 7 \cdot 23 \cdot 43 \cdot 47 \end{aligned}\text{。}

质因数之和为 2+3+7+23+43+47=1252 + 3 + 7 + 23 + 43 + 47 = 125

Note 2021=4347.2021 = 43 \cdot 47. If a=piei,a = \prod p_i^{e_i}, then σ(an)=σ(piein),\sigma(a^n) = \prod \sigma(p_i^{e_i n}), so it suffices (and is necessary, taking aa prime) that σ(pN)1,\sigma(p^N) \equiv 1, i.e. p+p2++pN0p + p^2 + \cdots + p^N \equiv 0 (mod4347),\pmod{43 \cdot 47}, for every prime pp and every multiple NN of n.n.

Fix q{43,47}.q \in \{43, 47\}. If qq divides pp the sum is 0.0. If p1(modq)p \equiv 1 \pmod q the sum is N,\equiv N, so choosing such a prime (Dirichlet) forces qq to divide n.n. Otherwise the sum is ppN1p1p \cdot \frac{p^N - 1}{p - 1} with p1p - 1 invertible, so we need pN1(modq);p^N \equiv 1 \pmod q; choosing pp to be a primitive root mod qq forces q1q - 1 to divide n.n. Conversely, if q(q1)q(q-1) divides nn then for every multiple NN of nn and every prime p,p, the sum vanishes mod qq in all three cases. Hence the least nn is n=lcm(4342, 4746)=237234347. \begin{aligned} n &= \operatorname{lcm}(43 \cdot 42,\ 47 \cdot 46) \\ &= 2 \cdot 3 \cdot 7 \cdot 23 \cdot 43 \cdot 47. \end{aligned}

The sum of the prime factors is 2+3+7+23+43+47=125.2 + 3 + 7 + 23 + 43 + 47 = 125.

第 13 题#13
完整试卷

其他年份的第 14 题