免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[数论] 最小素因子-易猜不易证

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

dddd,没头绪

TOP

本帖最后由 tommywong 于 2021-5-29 15:44 编辑

$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$

TOP

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


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

TOP

本帖最后由 tommywong 于 2021-5-29 15:59 编辑

回复 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$
2

评分人数

    • hbghlyj: 原来如此,学到了威望 + 1
    • realnumber: 没看出错误,@hbghlyj 来看看威望 + 1

TOP

返回列表 回复 发帖