特殊连续素数寻找

13^13=13(mod 17) ??
啥意思

13的13次方减去13是17的倍数
也就是要找出两个相邻的素数p和q
p的p次方再减去p是q的倍数

猜：
(p^p-p)MODq == 0
是否等同于这个条件
(p^2-p)MODq == 0

回复：3楼
看来mathe应该已经搜索了很大的范围了吧，
(p^p-p) === 0 (mod p+2)
这里涉及到p^p暂时还没想到好的处理方法。

p+2不一定是素数的.比如我给出的例子中17是13+4.
我只找出一个16比特的解,但是medie2005随后用我的程序找出了一个45位数的解.

#include <stdio.h>
#include <conio.h>
#define TRUE 1
#define FALSE 0
typedef int Bool;
typedef int Integer;/*便于需要时扩展成更大的整数类型*/
#define STRINT "%d"
Bool is_prime(Integer n);
Integer next_prime(Integer n);
Integer modpower(Integer p, Integer q);
/*
*作者：star
*时间：2010-01-19
*/
main(){
        Integer n = 2, next;
       
        for(;;){
             next = next_prime(n);
             if((modpower(n, next) - n) % next == 0){
                 printf(STRINT, n);
                 printf("\n");
                 printf(STRINT, next);
                 printf("\n");
             }
             n = next;
        }
       
        getch();
       
        return 0;
}
/*素数判断，只能判别大于1的数*/
Bool is_prime(Integer n){
      Integer i = 2;
     
      while(i * i <= n){
              if(n % i == 0){
                   return FALSE;
              }
              i++;
      }
      return TRUE;
}
/*求n后的第一个素数*/
Integer next_prime(Integer n){
     Integer next;
    
     next = (n % 2 == 0 ? n + 1 : n + 2);
    
     for(;;next += 2){
             if(is_prime(next) == TRUE){
                 break;
             }
     }
    
     return next;
}
/*求p的P次方除以q的余数，默认p < q*/
Integer modpower(Integer p, Integer q){
     Integer i, result = 1;
    
     for(i = 0; i < p; i++){
           result = (result * p) % q;
     }
    
     return result;
}


下一对是81101，81119

(09:14) gp > Mod(81101,81119)^81101
%4 = Mod(25256, 81119)
结果不对

实际上下一个解为p=65521,q=65537,并不是很难找到.
当然,第三个解就不容易寻找了
在
http://bbs.emath.ac.cn/viewthread.php?tid=2081&page=1&fromuid=20#pid25421
中,medie2005找到了第三组解:p=423746628825757810583848581127700861565685549,
q=423746628825757810583848581127700861565685607 计算花费了计算机约10分钟