The Prime Glossary: Euler probable prime

Euler probable prime
(another Prime Pages' Glossary entries)

Glossary:

Prime Pages:

Top 5000:

Fermat's little theorem tells us that if the integer a is not divisible by the prime p, then a^p^-1 is one modulo p. Euler was able to prove the stronger statement: a^(p-1)/2 = (a|p) (mod p) where (a|p) is the Jacobi symbol. So we can use this as a test for probable primality: given relatively prime integers a and n, we say n is an Euler probable prime (base a)(an Euler PRP) if

a^(n-1)/2 = (a|n) (mod n).

If this is the case and n is composite, then we say n is an Euler pseudoprime (base a).

There are 101,629 pseudoprimes base two less than 1,000,000,000,000 and roughly half: 53,332 are Euler pseudoprimes (22,407 of these are strong pseudoprimes). Since the Jacobi symbol is very easy to calculate, this gives us a test for primality that is roughly twice a s strong as a weak Fermat test, but a very little extra cost.

Below is a table of the odd composite Euler PRP's less than 3000 and the percentage of the odd composites in this range that are not exposed as composite by this test.

base composite odd Euler PRP's < 3000 percentage

2 561, 1105, 1729, 1905, 2047, 2465 0.6%

3 121, 1729, 2821 0.3%

5 781, 1541, 1729 0.3%

7 25, 703, 2101,2353, 2465 0.5%

11 133, 793, 2465 0.3%

13 105, 1785 0.2%

17 9, 145, 781, 1305, 2821 0.5%

19 9, 45, 49, 169, 1849, 2353 0.6%

23 169, 265, 553, 1729, 2465 0.5%

29 91, 341, 469, 871, 2257 0.5%

31 15, 49, 133, 481, 2465 0.5%

37 9, 451, 469, 589, 817, 1233, 1333, 1729 0.7%

41 21, 105, 841, 1065, 1281, 1417, 2465, 2701 0.7%

43 21, 25, 185, 385, 1541, 1729, 2465, 2553, 2849 0.8%

47 65, 341, 345, 703, 721, 897, 1105, 1649, 1729, 1891, 2257, 2465 1.1%

53 9, 91, 117, 1441, 1541, 2209, 2529, 2863 0.7%

59 145, 451, 1141, 1247, 1541, 1661, 1991, 2413, 2465 0.8%

61 15, 217, 341, 1261, 2465, 2821 0.6%

67 33, 49, 217, 561, 1105, 1309, 1519, 1729, 2209 0.8%

Related pages (outside of this work)

Fermat, Probable Primality and Pseudoprimes
composite probable primes to 10¹² (by various definitions)

References:

PSW80
C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 10⁹," Math. Comp., 35:151 (1980) 1003-1026. MR 82g:10030 [See Richard Pinch's lists of pseudoprimes and [Jaeschke93].]
Ribenboim95
P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, New York, NY, 1995. pp. xxiv+541, ISBN 0-387-94457-5. MR 96k:11112 [An excellent resource for those with some college mathematics. Basically a Guinness Book of World Records for primes with much of the relevant mathematics. The extensive bibliography is seventy-five pages.]