# Euler pseudoprime

In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and

$a^{(n-1)/2} \equiv \pm 1\pmod{n}$

(where mod refers to the modulo operation).

The motivation for this definition is the fact that all prime numbers p satisfy the above equation which can be deduced from Fermat's little theorem. Fermat's theorem asserts that if p is prime, and coprime to a, then ap−1 = 1 (mod p). Suppose that p>2 is prime, then p can be expressed as 2q + 1 where q is an integer. Thus; a(2q+1) − 1 = 1 (mod p) which means that a2q − 1 = 0 (mod p). This can be factored as (aq − 1)(aq + 1) = 0 (mod p) which is equivalent to a(p−1)/2 = ±1 (mod p).

The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are twice as strong as tests based on Fermat's little theorem.

Every Euler pseudoprime is also a Fermat pseudoprime. It is not possible to produce a definite test of primality based on whether a number is an Euler pseudoprime because there exist absolute Euler pseudoprimes, numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are a subset of the absolute Fermat pseudoprimes, or Carmichael numbers, and the smallest absolute Euler pseudoprime is 1729 = 7×13×19.

## Relation to Euler-Jacobi pseudoprimes

The slightly stronger condition that

$a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod n$

where n is an odd composite, the greatest common divisor of a and n equals 1, and (a/n) is the Jacobi symbol, is the more common definition of an Euler pseudoprime. See, for example, page 115 of the book by Koblitz listed below, page 90 of the book by Riesel, or page 1003 of.[1] A discussion of numbers of this form can be found at Euler–Jacobi pseudoprime. There are no absolute Euler-Jacobi pseudoprimes.

Euler pseudoprimes to base 2 are

341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481, 10261, 10585, 12801, 15709, 15841, 16705, 18705, ... (sequence A006970 in OEIS)

## Least Euler pseudoprime to base n

 n Least EPSP n Least EPSP n Least EPSP n Least EPSP 1 9 33 545 65 33 97 21 2 341 34 21 66 65 98 9 3 121 35 9 67 33 99 25 4 341 36 35 68 25 100 9 5 217 37 9 69 35 101 25 6 185 38 39 70 69 102 133 7 25 39 133 71 9 103 51 8 9 40 39 72 85 104 15 9 91 41 21 73 9 105 451 10 9 42 451 74 15 106 15 11 133 43 21 75 91 107 9 12 65 44 9 76 15 108 91 13 21 45 133 77 39 109 9 14 15 46 9 78 77 110 111 15 341 47 65 79 39 111 55 16 15 48 49 80 9 112 65 17 9 49 25 81 91 113 21 18 25 50 21 82 9 114 115 19 9 51 25 83 21 115 57 20 21 52 51 84 85 116 9 21 65 53 9 85 21 117 49 22 21 54 55 86 65 118 9 23 33 55 9 87 133 119 15 24 25 56 33 88 87 120 77 25 217 57 25 89 9 121 15 26 9 58 57 90 91 122 33 27 65 59 15 91 9 123 85 28 9 60 341 92 21 124 25 29 15 61 15 93 25 125 9 30 49 62 9 94 57 126 25 31 15 63 341 95 141 127 9 32 25 64 9 96 65 128 49