login
Pseudoprimes to base 7.
(Formerly M4168)
18

%I M4168 #44 Jun 25 2021 12:09:21

%S 6,25,325,561,703,817,1105,1825,2101,2353,2465,3277,4525,4825,6697,

%T 8321,10225,10585,10621,11041,11521,12025,13665,14089,16725,16806,

%U 18721,19345,20197,20417,20425,22945,25829,26419,29234,29341,29857,29891,30025,30811,33227

%N Pseudoprimes to base 7.

%C According to _Karsten Meyer_, May 16 2006, 6 should be excluded, following the strict definition in Crandall and Pomerance.

%C Theorem: If both numbers q & 2q-1 are primes(q is in the sequence A005382) and n=q*(2q-1) then 7^(n-1)==1 (mod 7)(n is in the sequence) iff q=2 or mod(q,14) is in the set {1, 5, 13}. 6,703,18721,38503,88831,104653,146611,188191,... are such terms. This sequence is a subsequence of A122784. - _Farideh Firoozbakht_, Sep 14 2006

%C Composite numbers n such that 7^(n-1) == 1 (mod n).

%D R. Crandall and C. 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)

%D R. K. Guy, Unsolved Problems in Number Theory, A12.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H R. J. Mathar, T. D. Noe and Hiroaki Yamanouchi, <a href="/A005938/b005938.txt">Table of n, a(n) for n = 1..87448</a> (terms a(1)-a(697) from R. J. Mathar, a(698)-a(1000) from T. D. Noe)

%H J. Bernheiden, <a href="http://www.mathe-schule.de/download/pdf/Primzahl/PSP.pdf">Pseudoprimes (Text in German)</a>

%H C. Pomerance & N. J. A. Sloane, <a href="/A001567/a001567_4.pdf">Correspondence, 1991</a>

%H F. Richman, <a href="http://math.fau.edu/Richman/carm.htm">Primality testing with Fermat's little theorem</a>

%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>

%t Select[Range[31000], ! PrimeQ[ # ] && PowerMod[7, (# - 1), # ] == 1 &] (* _Farideh Firoozbakht_, Sep 14 2006 *)

%o (Python)

%o from sympy import isprime

%o def ok(n): return pow(7, n-1, n) == 1 and not isprime(n)

%o print(list(filter(ok, range(1, 34000)))) # _Michael S. Branicky_, Jun 25 2021

%Y Pseudoprimes to other bases: A001567 (2), A005935 (3), A005936 (5), A005937 (6), A005939 (10).

%Y Cf. A005382, A122784.

%K nonn

%O 1,1

%A _N. J. A. Sloane_.