Question

求 $2019^8 + 1$ 的最小奇质因数。

Find the least odd prime factor of $2019^8 + 1.$

答案

答案：97

知识点：乘法阶模幂运算

难度评级：2990

小提示：

若 $p$ 整除 $2019^8 + 1$ ，则 $2019^8 \equiv -1 \pmod{p}$ ，所以 $2019$ 模 $p$ 的阶恰好为 $16$

If $p$ divides $2019^8 + 1,$ then $2019^8 \equiv -1 \pmod{p},$ so the order of $2019$ modulo $p$ is exactly $16$

大提示：

阶整除 $p - 1$ ，所以 $p \equiv 1 \pmod{16}$ ；用反复平方检验最小的这类质数中 $2019 \bmod p$ 的情况

The order divides $p - 1,$ so $p \equiv 1 \pmod{16};$ test the smallest such primes by repeated squaring of $2019 \bmod p$

解答：

设奇质数 $p$ 整除 $2019^8 + 1$ 。则 $2019^8 \equiv -1 \pmod{p}$ ，所以 $2019^{16} \equiv 1$ ，但 $2019^8 \not\equiv 1$ ： $2019$ 模 $p$ 的乘法阶恰好为 $16$ 。由于阶整除 $p - 1$ ，必须有 $p \equiv 1 \pmod{16}$ 。最小的这类质数是 $17$ 与 $97$ 。

模 $17$ 时， $2019 \equiv 13$ ，且 $13^2 = 169 \equiv -1$ ，所以 $2019^8 \equiv (-1)^4 = 1$ ，从而 $2019^8 + 1 \equiv 2 \neq 0$ 。模 $97$ 时， $2019 \equiv -18$ ，反复平方， $\begin{aligned} 2019^2 &\equiv 324 \equiv 33, \\ 2019^4 &\equiv 33^2 = 1089 \\ &\equiv 22, \\ 2019^8 &\equiv 22^2 = 484 \\ &\equiv -1 \pmod{97} \end{aligned}\text{。}$

所以 $97$ 整除 $2019^8 + 1$ ，并且它是最小奇质因数： $97$ 。

Suppose an odd prime $p$ divides $2019^8 + 1.$ Then $2019^8 \equiv -1 \pmod{p},$ so $2019^{16} \equiv 1$ while $2019^8 \not\equiv 1:$ the multiplicative order of $2019$ modulo $p$ is exactly $16.$ Since the order divides $p - 1,$ we need $p \equiv 1 \pmod{16},$ and the smallest such primes are $17$ and $97.$

Modulo $17:$ $2019 \equiv 13,$ and $13^2 = 169 \equiv -1,$ so $2019^8 \equiv (-1)^4 = 1$ and $2019^8 + 1 \equiv 2 \neq 0.$ Modulo $97:$ $2019 \equiv -18,$ and squaring repeatedly, $\begin{aligned} 2019^2 &\equiv 324 \equiv 33, \\ 2019^4 &\equiv 33^2 = 1089 \\ &\equiv 22, \\ 2019^8 &\equiv 22^2 = 484 \\ &\equiv -1 \pmod{97}. \end{aligned}$

So $97$ divides $2019^8 + 1,$ and it is the least odd prime factor: $97.$

2019 AIME I 第 14 题

答案：97

难度评级：2990

小提示：

大提示：

解答：

其他年份的第 14 题