p^p=p mod(q)

medie2005 · 发表于 2010-1-18 10:47:56

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

Puzzle 521. p^p=p mod(q) One notices that 13^13=13mod(17) is of the form for two consecutive primes p,q p^p=p mod(q). Q. Find larger examples

mathe · 发表于 2010-1-18 10:59:04

q-p通常应该很小而 p^p=p(mod q) => (-p)^p=-p(mod q)=>(-p)^(q-p)=1(mod q) => (q-p)^(q-p)=1(mod q) 也就是说, q是$(q-p)^{q-p}-1$的因子,而q-p是一个比较小的偶数,比如因子分解$4^4-1$就可以找到q=17这个解

mathe · 发表于 2010-1-18 11:03:31

不过根据实际计算结果,很难找到这样的结果,即使没有要求两个素数连续,结果都很少

mathe · 发表于 2010-1-18 11:09:25

q=65537,p=65521满足条件

mathe · 发表于 2010-1-18 11:18:27

pari/gp代码

findp(N)=
{
local(w,x,f,y,b);
for(u=2,N,w=2*u;x=w^w-1;f=factor(x);
for(h=1,length(f[,1]),
y=f[h,1];
if(y>w&&isprime(y-w),
b=1;
for(t=2,w-2,
if(isprime(y-t), b=0;break())
);
if(b,print(y " " y-w))
)
)
)
}

复制代码

gxqcn · 发表于 2010-1-18 11:29:27

假设 r=MultiplicativeOrder[p, q]（r 是使 $p^r-=1 mod(q)$ 成立的最小正整数），则使 $p^p -=p mod(q)$ 成立的充分条件是 $r|(p-1)$；是否为必要条件尚不确定。

medie2005 · 发表于 2010-1-18 11:36:15

用mathe提供的程序，找到一组比较大的： p=423746628825757810583848581127700861565685549, q=423746628825757810583848581127700861565685607

mathe · 发表于 2010-1-18 11:40:13

哇,你算了多长的时间?用什么工具?

medie2005 · 发表于 2010-1-18 11:41:57

也就十分钟不到，就是用pari/gp啊。就是5楼的程序。

wayne · 发表于 2010-1-18 12:23:04

哇，很强悍，学习了

账号		自动登录	找回密码
密码			欢迎注册

[转载] p^p=p mod(q)

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分