论坛 › 算法交流 › p^p=p mod(q)

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

p^p=p mod(q)

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;
          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（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)