Question

对任意正整数 $a$ ， $\sigma(a)$ 表示 $a$ 的所有正整数因数之和。设 $n$ 是最小的正整数，使得对所有正整数 $a$ ， $\sigma(a^n) - 1$ 都能被 $2021$ 整除。求 $n$ 的质因数分解中所有质因数的和。

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

答案

答案：125

知识点：因数之和乘法阶最小公倍数模运算

难度评级：3270

解答：

注意 $2021 = 43 \cdot 47$ 。若 $a = \prod p_i^{e_i}$ ，则 $\sigma(a^n) = \prod \sigma(p_i^{e_i n})$ ，所以只需（且取 $a$ 为质数可知也必须）对每个质数 $p$ 以及每个 $n$ 的倍数 $N$ 都有 $\sigma(p^N) \equiv 1$ ，即 $p + p^2 + \cdots + p^N \equiv 0$ $\pmod{43 \cdot 47}$ ，

固定 $q \in \{43, 47\}$ 。若 $q \mid p$ ，则和为 $0$ 。若 $p \equiv 1 \pmod q$ ，则该和 $\equiv N$ ，所以选择这样的质数（由狄利克雷定理）会迫使 $q \mid n$ 。否则，和为 $p \cdot \frac{p^N - 1}{p - 1}$ ，其中 $p - 1$ 可逆，所以需要 $p^N \equiv 1 \pmod q$ ；选择模 $q$ 的一个原根质数会迫使 $q - 1 \mid n$ 。反过来，如果 $q(q-1) \mid n$ ，那么对每个 $n$ 的倍数 $N$ 和每个质数 $p$ ，该和在上述三种情形中都模 $q$ 为零。因此最小的 $n$ 为 $p$ ， $\begin{aligned} n &= \operatorname{lcm}(43 \cdot 42,\ 47 \cdot 46) \\ &= 2 \cdot 3 \cdot 7 \cdot 23 \cdot 43 \cdot 47. \end{aligned}$

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

Note $2021 = 43 \cdot 47.$ If $a = \prod p_i^{e_i},$ then $\sigma(a^n) = \prod \sigma(p_i^{e_i n}),$ so it suffices (and is necessary, taking $a$ prime) that $\sigma(p^N) \equiv 1,$ i.e. $p + p^2 + \cdots + p^N \equiv 0$ $\pmod{43 \cdot 47},$ for every prime $p$ and every multiple $N$ of $n.$

Fix $q \in \{43, 47\}.$ If $q \mid p$ the sum is $0.$ If $p \equiv 1 \pmod q$ the sum is $\equiv N,$ so choosing such a prime (Dirichlet) forces $q \mid n.$ Otherwise the sum is $p \cdot \frac{p^N - 1}{p - 1}$ with $p - 1$ invertible, so we need $p^N \equiv 1 \pmod q;$ choosing $p$ to be a primitive root mod $q$ forces $q - 1 \mid n.$ Conversely, if $q(q-1) \mid n$ then for every multiple $N$ of $n$ and every prime $p,$ the sum vanishes mod $q$ in all three cases. Hence the least $n$ is $\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.$

2021 AIME I 第 14 题

答案：125

难度评级：3270

解答：

其他年份的第 14 题