editing

approved

A base-2 Fermat pseudoprime is a composite number x such that 2^x = = 2 (mod x). For such an x, ord(2,x) is the smallest positive integer m such that 2^m = = 1 (mod x). For a number x to have order n, it must be a factor of 2^n-1 and not be a factor of 2^r-1 for r<n. Sequence A086249 lists the number of pseudoprimes of order n.

Max Alekseyev, <a href="/A086250/b086250.txt">Table of n, a(n) for n = 1..200</a>

(PARI) { a(n) = fordiv(2^n-1, d, if(d>1 && (d-1)%n==0 && !ispseudoprime(d) && znorder(Mod(2, d))==n, return(d)) ); 0 } /* Max Alekseyev, Jan 07 2015 */

approved

editing

_T. D. Noe (noe(AT)sspectra.com), _, Jul 14 2003

E. W. Eric Weisstein, 's World of Mathematics, <a href="http://mathworld.wolfram.com/Pseudoprime.html">The World of Mathematics: Pseudoprime</a>

hard,nonn,new

Table[d=Divisors[2^n-1]; num=0; i=1; done=False; While[m=d[[i]]; done=!PrimeQ[m]&&PowerMod[2, m, m]==2&&MultiplicativeOrder[2, m]==n; If[done, num=m]; !done&&i<Length[d], i++ ]; num, {n, 100}]

hard,nonn,new

Smallest base-2 Fermat pseudoprime x that has ord(2,x) = n, or 0 if one does not exist.

0, 0, 0, 0, 0, 0, 0, 0, 0, 341, 2047, 0, 0, 5461, 4681, 4369, 0, 1387, 0, 13981, 42799, 15709, 8388607, 1105, 1082401, 22369621, 0, 645, 256999, 10261, 0, 16843009, 1227133513, 5726623061, 8727391, 1729, 137438953471, 91625968981, 647089, 561

1,10

A base-2 Fermat pseudoprime is a composite number x such that 2^x = 2 mod x. For such an x, ord(2,x) is the smallest positive integer m such that 2^m = 1 mod x. For a number x to have order n, it must be a factor of 2^n-1 and not be a factor of 2^r-1 for r<n. Sequence A086249 lists the number of pseudoprimes of order n.

R. G. E. Pinch, <a href="ftp://ftp.dpmms.cam.ac.uk/pub/PSP/">Pseudoprimes and their factors (FTP)</a>

E. W. Weisstein, <a href="http://mathworld.wolfram.com/Pseudoprime.html">The World of Mathematics: Pseudoprime</a>

a(10) = 1 there is only 1 pseudoprime, 341 = 11*31, having order 10; that is, 2^10 = 1 mod 341.

Table[d=Divisors[2^n-1]; num=0; i=1; done=False; While[m=d[[i]]; done=!PrimeQ[m]&&PowerMod[2, m, m]==2&&MultiplicativeOrder[2, m]==n; If[done, num=m]; !done&&i<Length[d], i++ ]; num, {n, 100}]

Cf. A001567 (base-2 pseudoprimes), A086249.

hard,nonn

T. D. Noe (noe(AT)sspectra.com), Jul 14 2003

approved