# Euler probable prime

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**(an Euler PRP) if

*a*)a^{(n-1)/2}= (a|n) (modn).

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. SelfridgeandWagstaff, Jr., S. S., "The pseudoprimes to 25 · 10^{9},"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.]