最小素因子-易猜不易证

hbghlyj

给定质数p,求S=$(p-1)^p+1$的最小素因子
容易猜到就是p,但这套题我没有答案
验证了100以内素数，未发现特例

realnumber

dddd,没头绪

tommywong

$2\le q<p,~(q-1,p)=(q,p)=1$
假設$(p-1)^p\equiv -1\pmod{q}$
$(q,p-1)\neq 1\Rightarrow q\mid p-1\Rightarrow (p-1)^p\equiv 0\pmod{q}$
$(q,p-1)=1$
$(p-1)^{2p}\equiv 1\pmod{q}
\Rightarrow \color{red}{q-1\mid 2p}\Rightarrow q-1\mid 2\Rightarrow q=3$
$(p-1)^p\equiv p-1\equiv -1\pmod{3}\Rightarrow 3\mid p$

realnumber

$2\le q
tommywong 发表于 2021-5-29 11:46

谢谢,还是有2处没想明白,
最后2行中,$q-1\mid 2p$为什么可以推出来?
$(p-1)^p=p-1  (\mod 3)$这个怎么来的啊?

tommywong

回复 4# realnumber

做錯嘢，再睇過吖
$2\le q<p,~(q-1,p)=(q,p)=1$
假設$(p-1)^p\equiv -1\pmod{q}$
$(q,p-1)\neq 1\Rightarrow q\mid p-1\Rightarrow (p-1)^p\equiv 0\pmod{q}$
$(q,p-1)=1\Rightarrow (p-1)^{q-1}\equiv 1\pmod{q}$
$(p-1)^{2p}\equiv 1\pmod{q}$
$(p-1)^{(q-1,2p)}\equiv 1\pmod{q}$
$(q-1,2p)=(q-1,2)\mid 2$
$(p-1)^2\equiv 1\pmod{q}\Rightarrow (p-1)^p\equiv p-1\equiv -1\pmod{q}\Rightarrow q\mid p$