Question

设 $n$ 为最小正整数，使得 $149^n - 2^n$ 能被 $3^3 \cdot 5^5 \cdot 7^7$ 整除。求 $n$ 的正因数个数。

Let $n$ be the least positive integer for which $149^n - 2^n$ is divisible by $3^3 \cdot 5^5 \cdot 7^7.$ Find the number of positive divisors of $n.$

答案

答案：270

知识点：质因数分解乘法阶因数个数

难度评级：2920

解答：

按质数分别考虑。因为 $149 - 2 = 147 = 3 \cdot 7^2$ ，提幂引理给出 $v_3(149^n - 2^n)$ $= v_3(147) + v_3(n)$ $= 1 + v_3(n)$ ，并且 $v_7(149^n - 2^n) = 2 + v_7(n)$ 对每个正整数 $n$ 都成立。要求指数至少达到 $3$ 和 $7$ ，迫使 $3^2 \mid n$ 且 $7^5 \mid n$ 。

对于 $5$ ，首先需要 $149^n \equiv 2^n \pmod 5$ ，即 $4^n \equiv 2^n$ ，也就是 $2^n \equiv 1 \pmod 5$ ，这要求 $4 \mid n$ 。写 $n = 4k$ 。在 $149^4 - 2^4$ $= (149 - 2)(149 + 2)(149^2 + 4)$ 中，只有最后一个因子可被 $5$ 整除，且只整除一次，因为 $149^2 + 4 = 22205 = 5 \cdot 4441$ 。从底数 $149^4, 2^4$ 使用提幂引理，得 $v_5(149^n - 2^n) = 1 + v_5(k)$ ，所以 $5^4 \mid k$ ，即 $4 \cdot 5^4 \mid n$ 。

最小的有效 $n$ 为 $2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5$ ，它有 $(2+1)(2+1)(4+1)(5+1)$ $= 270$ 个正因数。

Work prime by prime. Since $149 - 2 = 147 = 3 \cdot 7^2,$ the lifting-the-exponent lemma gives $v_3(149^n - 2^n)$ $= v_3(147) + v_3(n)$ $= 1 + v_3(n)$ and $v_7(149^n - 2^n) = 2 + v_7(n)$ for every positive integer $n.$ Requiring at least $3$ and $7$ forces $3^2 \mid n$ and $7^5 \mid n.$

For $5$ we first need $149^n \equiv 2^n \pmod 5,$ i.e. $4^n \equiv 2^n,$ i.e. $2^n \equiv 1 \pmod 5,$ which requires $4 \mid n.$ Write $n = 4k.$ In $149^4 - 2^4$ $= (149 - 2)(149 + 2)(149^2 + 4),$ only the last factor is divisible by $5,$ and only once, since $149^2 + 4 = 22205 = 5 \cdot 4441.$ Lifting the exponent from the base $149^4, 2^4$ gives $v_5(149^n - 2^n) = 1 + v_5(k),$ so $5^4 \mid k,$ i.e. $4 \cdot 5^4 \mid n.$

The least valid $n$ is $2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5,$ which has $(2+1)(2+1)(4+1)(5+1)$ $= 270$ positive divisors.

2020 AIME I 第 12 题

答案：270

难度评级：2920

解答：

其他年份的第 12 题