Forgot password
 Register account
View 1978|Reply 4

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

[Copy link]

3200

Threads

7827

Posts

52

Reputation

Show all posts

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

412

Threads

1432

Posts

3

Reputation

Show all posts

realnumber posted 2021-5-28 20:56
dddd,没头绪

81

Threads

434

Posts

12

Reputation

Show all posts

tommywong posted 2021-5-29 11:46
Last edited by 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$

412

Threads

1432

Posts

3

Reputation

Show all posts

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

81

Threads

434

Posts

12

Reputation

Show all posts

tommywong posted 2021-5-29 15:56
回复 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$

Rate

Number of participants 2威望 +2 Collapse Reason
hbghlyj + 1 原来如此,学到了
realnumber + 1 没看出错误,@hbghlyj 来看看

View Rating Log

Quick Reply

Advanced Mode
B Color Image Link Quote Code Smilies
You have to log in before you can reply Login | Register account

$\LaTeX$ formula tutorial

Mobile version

2025-7-15 13:59 GMT+8

Powered by Discuz!

Processed in 0.013933 seconds, 24 queries