每日一题[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{ 位}}.\]

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复