Euler probable prime

Fermat's little theorem tells us that if the integer a is not divisible by the prime p, then ap-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%

See Also: StrongPRP, CarmichaelNumber, Pseudoprime, FrobeniusPseudoprime

References:

PSW80
C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 109," Math. Comp., 35:151 (1980) 1003-1026.  MR 82g:10030
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.]
Printed from the PrimePages <t5k.org> © Reginald McLean.