login
Fermat pseudoprimes to base 2 which are congruent to 1 (mod 8).
1

%I #26 Mar 31 2021 02:34:04

%S 561,1105,1729,1905,2465,4033,4369,4681,6601,8321,8481,10585,11305,

%T 12801,15841,16705,18705,18721,23001,23377,25761,30121,30889,31417,

%U 31609,33153,34945,39865,41041,41665,46657,52633,62745,65281,74665,75361,83665,85489

%N Fermat pseudoprimes to base 2 which are congruent to 1 (mod 8).

%C Old name was: Fermat pseudoprimes to base 2 of the form 8*p*n + p^2, where p is prime and n natural.

%C For p = 5 the formula becomes 40*n + 25. From the first 15 pseudoprimes divisible by 5, 12 are of the form 40*n + 25 (beside 3 of them which are of the form 40*n + 5). Conjecture: there are no pseudoprimes to base 2 of the form 40*n + 15.

%C Note: it can be seen that a pseudoprime can be written in this formula in more than one way: e.g., 561 = 8*3*23 + 3^2 = 8*11*5 + 11^2 = 8*17*2 + 17^2 or 1905 = 8*3*79 + 3^2 = 8*5*47 + 5^2.

%C Conjecture: If a Fermat pseudoprime to base 2 can be written as 8*p*n + p^2, where n is an integer and p one of its prime factors, then it can be written this way for any of its prime factors. Checked for all pseudoprimes from the sequence above.

%C Conjecture: If a Fermat pseudoprime to base 2 with two prime factors can be written as 8*p1*n + p1^2, where n is a natural number and p1 one of its two prime factors, then it can also be written as 8*p2*(-n) + p2^2, where p2 is the other prime factor. Checked for 4033 = 37*109(n = 9), 4369 = 17*257(n = 30), 4681 = 31*151(n = 15), 8321 = 53*157(n = 13), 18721 = 97*193(n = 12), 23377 = 97*241(n = 18), 31417 = 89*353(n = 33), 31609 = 73*433 (n = 45), 65281 = 97*673(n = 72), 85489 = 53*1613 (n = 195).

%C Conjecture: If a Fermat pseudoprime to base 2 cannot be written as 8*p*n + p^2, where n is an integer and p one of its prime factors, then it cannot be written this way for any of its prime factors. Checked for the following pseudoprimes: 341, 645, 1387, 2047, 2701, 2821, 3277, 4371, 5461, 7957, 10261, 13741, 13747, 13981, 14491, 15709, 19951, 29341, 31621, 42799, 49141, 49981, 55245, 60701, 60787, 63973, 65077, 68101, 72885, 80581, 83333.

%C Note: from the first 72 pseudoprimes, 39 can be written this way.

%C All three conjectures are true (obvious from new characterization). - _Charles R Greathouse IV_, Dec 07 2014

%H Amiram Eldar, <a href="/A218483/b218483.txt">Table of n, a(n) for n = 1..10000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FermatPseudoprime.html">Fermat Pseudoprime</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PouletNumber.html">Poulet Number</a>.

%p select(t -> 2 &^ t mod t = 2 and not isprime(t), [seq(1+8*j,j=0..10^5)]); # _Robert Israel_, Dec 07 2014

%t Select[8 * Range[10^4] + 1, PowerMod[2, # - 1, #] == 1 && CompositeQ[#] &] (* _Amiram Eldar_, Mar 30 2021 *)

%o (PARI) is(n)=n%8==1 && Mod(2,n)^n==2 && !isprime(n) \\ _Charles R Greathouse IV_, Dec 07 2014

%Y Cf. A001567, A216023, A214305.

%K nonn

%O 1,1

%A _Marius Coman_, Oct 30 2012

%E Corrected by _Charles R Greathouse IV_, Dec 07 2014

%E New name from _Charles R Greathouse IV_, Dec 07 2014