Generating all Fermat pseudoprimes incl. Carmichael numbers

THE PRIME NUMBER SERIES 26

A Fermat pseudoprime number is a natural number that passes the Fermat prime number test, although it is not a prime number but a composite number.

All Fermat pseudoprimes including the Carmichael numbers can be generated with:

$a^{bc-1} \equiv 1 \mod{bc}$

whereby $a, b, c \in \mathbb{N}$ with $b, c > 1$ and $0 < a< b*c$ and b, c are co-alien to a.

Note: For a=1, all composite natural numbers can be generated.

For a=2 there are the following Fermat pseudoprimes including the Carmichael numbers up to 1000000:

341,561,645,1105,1387,1729,1905,2047,2465,2701,2821,3277,4033,4369,

4371,4681,5461,6601,7957,8321,8481,8911,10261,10585,11305,12801,

13741,13747,13981,14491,15709,15841,16705,18705,18721,19951,

23001,23377,25761,29341,30121,30889,31417,31609,31621,33153,

34945,35333,39865,41041,41665,42799,46657,49141,49981,52633,

55245,57421,60701,60787,62745,63973,65077,65281,68101,72885,

74665,75361,80581,83333,83665,85489,87249,88357,88561,90751,

91001,93961,101101,104653,107185,113201,115921,121465,123251,

126217,129889,129921,130561,137149,149281,150851,154101,

157641,158369,162193,162401,164737,172081,176149,181901,

188057,188461,194221,196021,196093,204001,206601,208465,

212421,215265,215749,219781,220729,223345,226801,228241,

233017,241001,249841,252601,253241,256999,258511,264773,

266305,271951,272251,275887,276013,278545,280601,282133,

284581,285541,289941,294271,294409,314821,318361,323713,

332949,334153,340561,341497,348161,357761,367081,387731,

390937,396271,399001,401401,410041,422659,423793,427233,

435671,443719,448921,449065,451905,452051,458989,464185,

476971,481573,486737,488881,489997,493697,493885,512461,

513629,514447,526593,530881,534061,552721,556169,563473,

574561,574861,580337,582289,587861,588745,604117,611701,

617093,622909,625921,635401,642001,647089,653333,656601,

657901,658801,665281,665333,665401,670033,672487,679729,

680627,683761,688213,710533,711361,721801,722201,722261,

729061,738541,741751,742813,743665,745889,748657,757945,

769567,769757,786961,800605,818201,825265,831405,838201,

838861,841681,847261,852481,852841,873181,875161,877099,

898705,915981,916327,934021,950797,976873,983401,997633

This means that Fermat’s prime number test for a=2 only gives reliable results for all values from 3 to 1000000 with the exception of the aforementioned Fermat pseudoprimes and Carmichael numbers: prime or non-prime.

Munich, 27 May 2024

Gottfried Färberböck

Language:

Language:

THE PRIME NUMBER SERIES

Generating all Fermat pseudoprimes incl. Carmichael numbers