A020145 Pseudoprimes to base 17.

4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187, 4912, 5365, 5662, 5833, 6601, 6697, 7171, 8481, 8911, 10585, 11476, 12403, 12673, 13333, 13833, 15805, 15841, 16705, 19345, 19729, 20591, 21781, 22791

Offset: 1

Author

David W. Wilson

Keywords

• nonn

Comments

Composite numbers n such that 17^(n-1) == 1 (mod n).

According to Karsten Meyer, May 16 2006, the terms 4, 8, 9 and 16 should be excluded, following the strict definition in Crandall and Pomerance (p. 132) that even numbers and squares are not pseudoprimes regardless of congruence. [clarified by Alonso del Arte, Feb 17 2020]

Examples

			17^3 = 4913 = 1 mod 4, so 4 is in the sequence (note the Crandall and Pomerance caveat, however).
17^4 = 83521 = 1 mod 5, but 5 is actually prime, so it's not in the sequence.
17^5 = 1419857 = 5 mod 6, so 6 is not in the sequence either.
		

References

• Richard Crandall and Carl Pomerance, "Prime Numbers - A Computational Perspective", Second Edition, Springer Verlag 2005, ISBN 0-387-25282-7 Page 132 (Theorem 3.4.2. and Algorithm 3.4.3).

Links

• R. J. Mathar and T. D. Noe, Table of n, a(n) for n = 1..1000 (R. J. Mathar to 799 terms)
• Fred Richman, Primality testing with Fermat's little theorem
• Index entries for sequences related to pseudoprimes

Crossrefs

Cf. A001567 (pseudoprimes to base 2).

Programs

Mathematica

base = 17; pp17 = {}; n = 1; While[Length[pp17] < 100, n++; If[!PrimeQ[n] && PowerMod[base, n - 1, n] == 1, AppendTo[pp17, n]]]; pp17 (* T. D. Noe, Feb 21 2012 *)
Select[Range[23000], !PrimeQ[#] && PowerMod[17, # - 1, #] == 1 &] (* Harvey P. Dale, Apr 20 2019 *)