
Glossary: Prime Pages: Top 5000: 
GIMPS has discovered a new largest known prime number: 2^{82589933}1 (24,862,048 digits) 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.
See Also: StrongPRP, CarmichaelNumber, Pseudoprime, FrobeniusPseudoprime Related pages (outside of this work)
References:
Chris K. Caldwell © 19992019 (all rights reserved)
