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^{(p1)/2} =
(ap) (mod p) where
(ap) 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^{(n1)/2} = (an)
(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 Related pages (outside of this work) References:
 PSW80
 C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 10^{9}," Math. Comp., 35:151 (1980) 10031026. MR 82g:10030 [See Richard Pinch's lists of pseudoprimes and [Jaeschke93].]
 Ribenboim95
 P. Ribenboim, The new book of prime number records, 3rd edition, SpringerVerlag, New York, NY, 1995. pp. xxiv+541, ISBN 0387944575. 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 seventyfive pages.]
