A086019 For p = prime(n), a(n) is the largest prime q such that pq is a base-2 pseudoprime; that is, 2^(pq-1) = 1 mod pq; a(n) is 0 if no such prime exists.

0, 0, 0, 31, 0, 257, 73, 683, 113, 331, 109, 61681, 5419, 2796203, 1613, 3033169, 1321, 599479, 122921, 38737, 22366891, 8831418697, 2931542417, 22253377, 268501, 131071, 28059810762433, 279073, 54410972897, 77158673929, 145295143558111

Offset: 2

Author

T. D. Noe, Jul 08 2003

Keywords

• hard
• nonn

Comments

Using a theorem of Lehmer, it can be shown that the possible values of q are among the prime factors of 2^(p-1)-1. Sequence A085012 gives the smallest prime q such that 2^(pq-1) = 1 mod pq. Sequence A085014 gives the number of 2-factor pseudoprimes that have prime(n) as a factor.

Examples

			a(9) = 683 because prime(9) = 23 and 683 is the largest factor of 2^22-1 that yields a pseudoprime when multiplied by 23.
		

References

• Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 105-112.

Links

• Amiram Eldar, Table of n, a(n) for n = 2..337
• Paul Erdős, On the converse of Fermat's theorem, Amer. Math. Monthly 56 (1949), p. 623-624.
• D. H. Lehmer, On the converse of Fermat's theorem, Amer. Math. Monthly 43 (1936), p. 347-354.

Crossrefs

Cf. A001567 (base 2 pseudoprimes), A085012, A085014, A180471.

Programs

Mathematica

Table[p=Prime[n]; q=Reverse[Transpose[FactorInteger[2^(p-1)-1]][[1]]]; i=1; While[i<=Length[q]&&(PowerMod[2, p*q[[i]]-1, p*q[[i]]]>1), i++ ]; If[i>Length[q], 0, q[[i]]], {n, 2, 40}]