找回密码
 欢迎注册
查看: 16077|回复: 21

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

[复制链接]
发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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这个解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-18 11:03:31 | 显示全部楼层
不过根据实际计算结果,很难找到这样的结果,即使没有要求两个素数连续,结果都很少
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-18 11:09:25 | 显示全部楼层
q=65537,p=65521满足条件

评分

参与人数 1威望 +1 贡献 +1 收起 理由
medie2005 + 1 + 1 mathe太速度了

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-18 11:18:27 | 显示全部楼层
pari/gp代码

  1. findp(N)=
  2. {
  3.    local(w,x,f,y,b);
  4.    for(u=2,N,w=2*u;x=w^w-1;f=factor(x);
  5.      for(h=1,length(f[,1]),
  6.           y=f[h,1];
  7.           if(y>w&&isprime(y-w),
  8.              b=1;
  9.              for(t=2,w-2,
  10.                if(isprime(y-t), b=0;break())
  11.              );
  12.              if(b,print(y " " y-w))
  13.           )
  14.       )
  15.    )
  16. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-18 11:29:27 | 显示全部楼层
假设 r=MultiplicativeOrder[p, q](r 是使 $p^r-=1 mod(q)$ 成立的最小正整数),
则使 $p^p -=p mod(q)$ 成立的充分条件是 $r|(p-1)$;是否为必要条件尚不确定。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-1-18 11:36:15 | 显示全部楼层
用mathe提供的程序,找到一组比较大的:
p=423746628825757810583848581127700861565685549,
q=423746628825757810583848581127700861565685607
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-18 11:40:13 | 显示全部楼层
哇,你算了多长的时间?用什么工具?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-1-18 11:41:57 | 显示全部楼层
也就十分钟不到,就是用pari/gp啊。就是5楼的程序。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-18 12:23:04 | 显示全部楼层
哇 ,很强悍,学习了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 21:24 , Processed in 0.044297 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表