Euler Pseudoprimes

An odd composite number $ n $ is called an Euler pseudoprime with respect to an integer $ 1 < a < n $ that is coprime to $ n $ if it satisfies the following condition: \[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \pmod{n} \]

This property can be used to test whether an odd number $ n $ is prime by leveraging a specific number-theoretic criterion.

If we can find an integer $ a $, coprime to $ n $ (meaning $ \gcd(n, a) = 1 $), for which the following equation does not hold:

\[ \left( \frac{a}{n} \right) = a^{(n-1)/2} \pmod{n} \]

then $ n $ is not a prime number.

Here, $\left( \frac{a}{n} \right)$ represents the Legendre symbol, which encodes a special relationship between $ a $ and $ n $.

Note: The Legendre symbol equals $1$ if $ a $ is a quadratic residue modulo $ p $, meaning there exists an integer $ x $ such that $ x^2 \equiv a \pmod{p} $. If $ a $ is not a quadratic residue modulo $ p $, the Legendre symbol is $-1$. If $ p $ divides $ a $, the Legendre symbol is $0$. The Legendre symbol applies only when $ p $ is prime, but it can be generalized to composite numbers through the Jacobi symbol.

A Practical Example
The Connection Between Euler and Fermat Pseudoprimes
Note

A Practical Example

Consider the odd composite number $ n = 15 $.

We select an integer $ 1 < a < 15 $ that is coprime to $ n $.

For example, let’s choose $ a = 2 $.

$$ a=2 $$

The number 2 is coprime to 15 because they share no common divisors.

$$ \gcd(2,15) = 1 $$

Next, we check whether $ n $ qualifies as an Euler pseudoprime by verifying the condition.

\[ \left( \frac{a}{n} \right) = a^{(n-1)/2} \pmod{n} \]

Substituting $ a = 2 $ and $ n = 15 $:

\[ \left( \frac{2}{15} \right) = 2^{(15-1)/2} \pmod{15} \]

\[ \left( \frac{2}{15} \right) = 2^{7} \pmod{15} \]

\[ \left( \frac{2}{15} \right) = 128 \pmod{15} \]

Computing modulo 15, we get $ 128 \mod 15 = 8 $:

\[ \left( \frac{2}{15} \right) = 128 \equiv 8 \pmod{15} \]

Here, the Legendre symbol evaluates to $ \left( \frac{2}{15} \right) = 1 $.

Note: The result $ \left(\frac{2}{15}\right) = 1 $ implies that $ 2 $ is a "quadratic residue" relative to the factorization $ 15 = 3 \cdot 5 $. This follows from the broader concept of the Jacobi symbol, which extends to composite moduli.

Since $ 8 \neq 1 $, we conclude that $ 15 $ is not a prime number.

In essence, $ n $, despite being composite, "behaves" like a prime in relation to base $ a $.

The Connection Between Euler and Fermat Pseudoprimes

If a number $ n $ is an Euler pseudoprime in base $ b $, then it is also a Fermat pseudoprime in base $ b $.

Euler pseudoprimes form a more exclusive subset of Fermat pseudoprimes.

In other words, every Euler pseudoprime is also a Fermat pseudoprime, but not the other way around. Some Fermat pseudoprimes fail to meet the Euler criterion.

Note: Euler pseudoprimes impose a stricter condition than Fermat pseudoprimes because they require an additional quadratic property, encoded through the Legendre symbol.

By definition, an Euler pseudoprime satisfies:

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

where $\left(\frac{b}{n}\right)$ is the Legendre symbol.

Squaring both sides of this relation, we obtain:

\[ \left(b^{(n-1)/2}\right)^2 \equiv \left(\left(\frac{b}{n}\right)\right)^2 \pmod{n} \]

\[ b^{2 \cdot (n-1)/2} \equiv \left(\frac{b}{n}\right)^2 \pmod{n}. \]

\[ b^{n-1} \equiv \left(\frac{b}{n}\right)^2 \pmod{n}. \]

The Legendre symbol $ \left(\frac{b}{n}\right) $ can only take values of $ \pm1 $, so when squared, $ \left(\frac{b}{n}\right)^2 $ is always congruent to $ 1 $ modulo $ n $.

\[ b^{n-1} \equiv 1 \pmod{n} \]

This is precisely the definition of a Fermat pseudoprime in base $ b $.

Thus, every Euler pseudoprime is automatically a Fermat pseudoprime.

However, the reverse does not hold: not every Fermat pseudoprime qualifies as an Euler pseudoprime.

Example

The composite number $ n = 91 $ is a Fermat pseudoprime in base $ a = 3 $ because it satisfies Fermat’s theorem:

$$ a^{p-1} \equiv 1 \pmod{p} $$

$$ 3^{90} \equiv 1 \pmod{91} $$

However, it is not an Euler pseudoprime in base $ a = 3 $ because it does not satisfy the stricter condition:

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

\[ 3^{45} \equiv \left(\frac{3}{91}\right) \pmod{91} \]

Note: Conversely, the composite number $ n = 341 $ is both an Euler pseudoprime and a Fermat pseudoprime in base $ a = 2 $.

Note

Additional notes and observations on Euler pseudoprimes.

Euler pseudoprimes produce fewer false positives than Fermat pseudoprimes
Let $ n $ be a positive, odd composite integer. The number of bases $ b < n $ that are coprime to $ n $ and for which $ n $ behaves as an Euler pseudoprime is at most half of all bases $ b $ satisfying $ \gcd(b, n) = 1 $.
This means that Euler pseudoprimes are more reliable than Fermat pseudoprimes in primality testing because they are based on a stricter condition. In contrast, with Fermat pseudoprimes, the number of false positives is "at least half" of all coprime bases. In some cases, such as Carmichael numbers, every coprime base produces a false positive. As a result, Fermat pseudoprimes generate significantly more false positives.
Existence of a Quadratic Non-Residue
For any odd integer $ n > 1 $ that is not a perfect square, there always exists a positive integer $ b < n $, coprime to $ n $, such that $ b $ is a quadratic non-residue modulo $ n $. In other words, its Legendre symbol satisfies $ \left( \frac{b}{n} \right) = -1 $.
Every Odd Composite Number Fails the Euler Test for at Least One Base
For any odd composite number $ n $, there is always at least one integer $ b < n $, coprime to $ n $, for which $ n $ does not pass the Euler pseudoprime test.

And so on.