Non-Universality Theorem for Euler Pseudoprimes
For every odd composite number \( n \), there exists at least one integer \( b < n \), coprime to \( n \), for which \( n \) is not an Euler pseudoprime.
This property demonstrates that not all odd composite numbers behave like Euler pseudoprimes for every coprime base.
In other words, for any composite number \( n \), there is always at least one base \( b \) that exposes \( n \) as not being an Euler pseudoprime.
\[ b^{(n-1)/2} \not\equiv \left( \frac{b}{n} \right) \pmod{n} \]
Simply put, there are no Carmichael numbers for the Euler test—no composite number is an Euler pseudoprime for all coprime bases.
What Are Euler Pseudoprimes? An odd composite number \( n \) is called an Euler pseudoprime if, for every base \( b \) coprime to \( n \) in the range \( 1<b<n \), it satisfies the Euler criterion: \[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \pmod{n} \] Here, \(\left( \frac{b}{n} \right) \) is the Jacobi symbol, which takes only the values \( \pm 1 \). \[ b^{(n-1)/2} \equiv \pm 1 \pmod{n} \]
A Practical Example
Let’s consider \( n = 21 \), an odd composite number.
\[ 21 = 3 \times 7 \]
We now check whether \( 21 \) is an Euler pseudoprime for various bases, meaning all integers \( b \) coprime to \( n=21 \) in the range \( 1<b<21 \).
To do this, we need to pick a number coprime to 21—one that is not divisible by 3 or 7.
The integers coprime to \( n = 21 \) are: \( \{ 1, 2, 4, 5, 7, 8, 10, 11, 13, 15, 16, 17, 19, 20 \} \).
Let's choose \( b = 2 \) as our test base.
Now, we check whether it satisfies the Euler criterion:
\[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \pmod{n} \]
\[ 2^{(21-1)/2} \equiv \left( \frac{2}{21} \right) \pmod{21} \]
\[ 2^{10} \equiv \left( \frac{2}{21} \right) \pmod{21} \]
Since \( 2^{10} = 1024 \), we compute:
\[ 1024 \equiv \left( \frac{2}{21} \right) \pmod{21} \]
Modulo 21, 1024 leaves a remainder of 16.
\[ 16 \equiv \left( \frac{2}{21} \right) \pmod{21} \]
At this point, we can already conclude that \( n = 21 \) is not an Euler pseudoprime for base \( b = 2 \), since the left-hand side evaluates to 16, whereas the Jacobi symbol on the right-hand side can only be \( \pm 1 \).
Note: For completeness, let’s explicitly compute the Jacobi symbol \( \left( \frac{2}{21} \right) \). The calculation involves factoring 21 into primes: \[ \left( \frac{2}{21} \right) = \left( \frac{2}{3} \right) \times \left( \frac{2}{7} \right) \] This breaks the problem into two Legendre symbols, which we can compute separately. Since \( \left( \frac{2}{3} \right) = -1 \) (as 2 is not a quadratic residue modulo 3) and \( \left( \frac{2}{7} \right) = 1 \) (since 2 is a quadratic residue modulo 7), we find: \[ \left( \frac{2}{21} \right) = \left( \frac{2}{3} \right) \times \left( \frac{2}{7} \right) = (-1) \times (1) = -1 \] Thus, the Jacobi symbol evaluates to -1, and since 16 is not congruent to -1 modulo 21, the Euler criterion fails. \[ 16 \equiv \left( \frac{2}{21} \right) \pmod{21} \] \[ 16 \not\equiv -1 \pmod{21} \] This confirms that \( 21 \) is not an Euler pseudoprime for base \( 2 \).
This example illustrates the key point: every odd composite number fails the Euler test for at least one base \( b \), just as the theorem states.
Proof
I'll use a proof by contradiction, assuming the opposite to be true: the odd composite number \( n \) is an Euler pseudoprime in every base \( b \) less than \( n \) and coprime to \( n \).
If that were the case, the number of false positives (misleading bases) would be exactly equal to the number of bases coprime to \( n \), which is given by \( \phi(n) \).
Here, \( \phi(n) \) represents the Euler totient function of \( n \).
However, it is already known that the bases in which \( n \) behaves as an Euler pseudoprime account for at most half of its coprime bases, meaning they can be at most \( \frac{\phi(n)}{2} \).
Thus, a contradiction arises because it is impossible for \( n \) to be an Euler pseudoprime for all coprime bases.
\[ \frac{\phi(n)}{2} \lt \phi(n) \]
Therefore, the initial assumption—that an odd composite number \( n \) is an Euler pseudoprime for all coprime bases—must be false.
It follows that the opposite must be true: there exists at least one base \( b \) for which \( n \) fails to be an Euler pseudoprime.
And that completes the proof.
