Euler's Non-Pseudoprimality Property for Composite Numbers

Let \( n \) be a positive, odd composite number. 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 \).

In other words, a composite number \( n \) can only mimic a prime (acting as an Euler pseudoprime) for a minority of bases \( b \), meaning those numbers coprime to \( n \) in the range \( 1 < b < n \).

This significantly limits the chances of \( n \) falsely passing Euler’s primality test.

As a result, Euler pseudoprimes yield fewer false positives than Fermat pseudoprimes, making them a more reliable tool for primality testing.

Note: Euler pseudoprimes are more effective than Fermat pseudoprimes at identifying prime numbers because Euler’s test filters out more non-primes that might otherwise appear prime. With Euler pseudoprimes, "at most half" of the coprime bases produce false positives, whereas with Fermat pseudoprimes, the proportion can be "at least half," leading to significantly more false positives. In certain cases, such as Carmichael numbers, every coprime base of a composite number produces a false positive.

A Practical Example

Let’s examine \( n = 15 \), which is an odd, positive composite number. Its prime factors are \( 3 \) and \( 5 \):

$$ n = 15 = 3 \cdot 5 $$

First, we list the numbers coprime to \( n \), meaning those integers \( b \) for which \( \gcd(b, 15) = 1 \).

The numbers \( b \) less than \( n = 15 \) are:

$$ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 $$

Now, we eliminate those that are not coprime to \( n \), meaning those divisible by \( 3 \) or \( 5 \):

Numbers divisible by 3: \( 3, 6, 9, 12 \)

Numbers divisible by 5: \( 5, 10 \)

Thus, the coprime numbers \( b \) with \( 15 \) are:

$$ 1, 2, 4, 7, 8, 11, 13, 14 $$

In total, there are \( \phi(15) = 8 \) numbers coprime to \( 15 \), where \( \phi \) represents the Euler totient function.

Which of these bases make 15 an Euler pseudoprime?

Now, we check for which bases \( b \) the number \( 15 \) behaves as an Euler pseudoprime.

The condition for \( 15 \) to be an Euler pseudoprime in base \( b \) is:

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

Base	Euler’s Condition	15 as an Euler Pseudoprime
base	Condizione di Eulero	Base in cui 15 è Pseudoprimo
\( b = 1 \)	\( 1^7 \equiv 1 \pmod{15} \)	✅ Yes (false positive)
\( b = 2 \)	\( 2^7 \equiv 8 \pmod{15} \)	❌ no
\( b = 4 \)	\( 4^7 \equiv 4 \pmod{15} \)	❌ no
\( b = 7 \)	\( 7^7 \equiv 7 \pmod{15} \)	❌ no
\( b = 8 \)	\( 8^7 \equiv 8 \pmod{15} \)	❌ no
\( b = 11 \)	\( 11^7 \equiv 11 \pmod{15} \)	❌ no
\( b = 13 \)	\( 13^7 \equiv 13 \pmod{15} \)	❌ no
\( b = 14 \)	\( 14^7 \equiv 14 \pmod{15} \)	❌ no

Among the 8 coprime bases for \( 15 \), only 1 (\( b = 1 \)) satisfies Euler’s pseudoprime condition.

In other words, we’ve identified just one false positive—a composite number that incorrectly passes the primality test.

Since this is well below half of the 8 bases, it confirms our initial claim.

And so on.