每日一题[2161]费马小定理

$2019^8+1$ 的最小奇质因数为_______．

答案    $97$．

解析    设质数 $p>2$ 且 $p\mid 2019^8+1$，则 $$2019^8\equiv -1\pmod p\implies 2019^{16}\equiv 1\pmod p,$$ 若 $1\leqslant m\leqslant 15$ 且 $2019^{m}\equiv 1\pmod p$，那么有 $$2019^{\gcd(m,16)}\equiv 1\pmod p,$$ 而 $2019^8\equiv -1\pmod p$，因此 $\gcd(m,16)\nmid 8$，进而 $m=16$ 是使得 $2019^{m}\equiv 1\pmod p$ 成立的最小正整数．根据费马小定理，有 $$2019^{p-1}\equiv 1\pmod p,$$ 因此 $p=16k+1$（$k\in\mathbb N$），因此 $p$ 可能为 $17,97,\cdots$． 先尝试 $p=17$，此时有 $$2019^8\equiv 13^8=169^4\equiv (-1) ^4=1\pmod {17},$$ 不符合题意． 再尝试 $p=97$，此时有 $$2019^8\equiv (-18)^8=324^4\equiv 33^4=1089^2\equiv 22^2=484\equiv -1\pmod{97},$$ 符合题意． 因此所求的最小奇质因数为 $97$． 事实上，有 $$2019^8+1=2\cdot 97\cdot \underbrace{1423275002072658812388593}_{25\text{ 位}}.$$