求证梅森合数与费马合数都通过了以2为底的miller rabin测试！

nyy

梅森合数=当p为素数的时候，2^p-1也是合数的情况（排除梅森素数），梅森数是素数肯定能通过以2为底的miller rabin测试！
费马合数=就是费马数为合数的情况，费马数是素数肯定能通过以2为底的miller rabin测试！

请证明这两种情况都能通过以2为底的miller rabin测试！

nyy

先看费马合数的问题：

1. Clear["Global`*"];
   
2. n=2^(2^7)+1;
   
3. Do[ a=PowerMod[2,2^k,n];
   
4.     If[a==n-1,a=-1];
   
5.     Print[{k,a}];
   
6.     If[Or[a==1,a==-1],Break[]],
   
7. {k,0,200}]
   

复制代码

求解结果

{0,2}
{1,4}
{2,16}
{3,256}
{4,65536}
{5,4294967296}
{6,18446744073709551616}
{7,-1}

简单起见：
n=2^(2^7)+1=2^128+1
n-1=2^128=2^121*2^7
2^(2^7)=-1(mod n)
所以费马合数肯定能通过这个测试了
其余同理费马合数都可以证明

nyy

梅森合数的情况
简单起见
n=2^67-1
n-1=2^67-1-1=2*(2^66-1)
根据费马小定理
(2^66-1)=0 (mod 67)
假设2^66-1=t*67(很显然t是一个奇数)
所以2^(2^66-1)=2^(t*67)=(2^67)^t=1^t=1 (mod n)
所以肯定通过了这个测试，以此类推！

nyy

我以为这会是个难题，没想到我自己好好想还是能想出来的！