Fermat Psedoprime

Author

Eric W. Weisstein
July 8, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/PrimeNumbers/FermatPseudoprime.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/FermatPseudoprime.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Enumeration

Table[{b,Select[Flatten[Position[Table[PowerMod[b,n-1,n],{n,10^4}],1]],!PrimeQ[#]&]},{b,2,5}]//ColumnForm

Eric

FermatPseudoprimes[b_:2,nmax_]:=Select[Flatten[Position[Table[PowerMod[b,n-1,n],{n,nmax}],1]],!PrimeQ[#]&]

Length[l1=FermatPseudoprimes[2,10^6]]//Timing

Maxim 1

FermatPseudoprimes2[a_,n_]:=Module[{L=Range[3,n,2]},L=Pick[L,Thread[Thread[!PrimeQ[L]]]];Pick[L,PowerMod[a,L-1,L],1]]

Length[l2=FermatPseudoprimes2[2,10^6]]//Timing

l1==l2

Maxim 2

Length[l3=Module[{L=Range[3,10^6,2],p},
p=Pick[L,PowerMod[2,L-1,L],1];
Pick[p,PrimeQ[p],False]]
]//Timing

l3==l1

Less Then Powers of 10

psp2

(psp2=Select[Flatten[Position[Table[PowerMod[2,n-1,n],{n,10^6}],1]],!PrimeQ[#]&]);//Timing

Select[Complement[Range[10^6],Prime[Range[PrimePi[10^6]]]],PowerMod[2,#-1,#]==1&];//Timing

(psp2=Select[Flatten[Position[Table[PowerMod[2,n-1,n],{n,10^8}],1]],!PrimeQ[#]&]);//Timing

Table[Count[psp2,_?(#<10^n&)],{n,8}]

psp3

(psp3=Select[Flatten[Position[Table[PowerMod[3,n-1,n],{n,10^8}],1]],!PrimeQ[#]&]);//Timing

Table[Count[psp3,_?(#<10^n&)],{n,8}]

Table[Count[Intersection[psp2,psp3],_?(#<10^n&)],{n,8}]

psp5

(psp5=Select[Flatten[Position[Table[PowerMod[5,n-1,n],{n,10^8}],1]],!PrimeQ[#]&]);//Timing

Table[Count[psp5,_?(#<10^n&)],{n,8}]

Table[Count[Intersection[psp2,psp3,psp5],_?(#<10^n&)],{n,8}]

psp7

(psp7=Select[Flatten[Position[Table[PowerMod[7,n-1,n],{n,10^8}],1]],!PrimeQ[#]&]);//Timing

Table[Count[psp7,_?(#<10^n&)],{n,8}]

Table[Count[Intersection[psp2,psp3,psp5,psp7],_?(#<10^n&)],{n,8}]