MAS3008 NUMBER THOERY

SOME STATISTICS ON PRIMES & PSEUDOPRIMES ETC

Up to 25 × 10^{9} there are:

just over 10^{7} primes; 21 853 pseudoprimes to base 2; 2 163 Carmichael numbers.

There are only 4 842 strong pseudoprimes to base 2 (e.g. 2047 = 23 × 89); 184 strong pseudoprimes to bases 2 and 3 (e.g. 1 373 653); 13 strong pseudoprimes to bases 2, 3 and 5; 1 strong pseudoprime to bases 2, 3, 5 and 7; no strong pseudoprimes to bases 2, 3, 5, 7 and 11.

One can show that if n is composite then n is a strong pseudoprime for at most 1/4 of the possible bases a with 1 < a < n. (See K.H. Rosen: Elementary Number Theory and its Applications, 3rd edition, Theorem 5.10, p.197 and p.302).

Thus there are no “strong Carmichael numbers”.

Nigel Byott November 2002