Existence of a Quadratic Non-Residue in Euler Pseudoprimes

For any odd number $ 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 $.

Here, a perfect square is simply a number that results from squaring an integer.

This property ensures that in any odd, non-square number, there is always at least one quadratic non-residue.

Note. This has key applications in probabilistic primality tests, particularly those based on Euler’s congruence. For instance, it strengthens primality testing by detecting composite numbers that might pass weaker tests, such as Fermat’s. It also prevents Carmichael numbers from passing Euler’s test, making it more reliable. Furthermore, this principle underpins many advanced probabilistic tests, including Miller-Rabin and Solovay-Strassen.

A Practical Example
Proof

A Practical Example

Let's consider $ n = 15 $, an odd number that is not a perfect square.

We need to find an integer $ b < 15 $, coprime to 15, such that its Legendre symbol satisfies $ \left( \frac{b}{15} \right) = -1 $, meaning $ b $ is a quadratic non-residue modulo $ n $.

First, we factorize $ n $ into primes:

\[ n = 15 = 3^1 \cdot 5^1. \]

The prime factors of $ n=15 $ are $ p = 3 $ and $ m = 5 $.

Next, we examine the quadratic residues modulo 3:

$ 0^2 = 0 \equiv 0 \pmod{3} $
$ 1^2 = 1 \equiv 1 \pmod{3} $
$ 2^2 = 4 \equiv 2 \pmod{3} $

The quadratic residues modulo 3 are $ \{1\} $, while the non-residues are $ \{2\} $.

We choose $ t = 2 $, since it is not a quadratic residue modulo 3.

Note. A quadratic residue modulo $ n $ is an integer $ a $ for which there exists some integer $ x $ satisfying: \[ x^2 \equiv a \pmod{n} \] In other words, $ a $ is a quadratic residue modulo $ n $ if there exists an $ x $ whose square is congruent to $ a $ modulo $ n $. Otherwise, $ a $ is a quadratic non-residue.

Now, we construct a system of congruences to find an integer $ b $ that is a quadratic residue modulo 5 and a non-residue modulo 3:

$$ \begin{cases} b \equiv 1 \pmod{5} \\ \\ b \equiv 2 \pmod{3} \end{cases} $$

The first equation ensures that $ b $ is a square modulo 5.

The second equation guarantees that $ b \equiv 2 \pmod{3} $ is a non-square modulo 3, since we already established that 2 is not a quadratic residue in this case.

Solving this system, we find $ b=11 $, which satisfies both conditions.

$$ \begin{cases} 11 \equiv 1 \pmod{5} \\ \\ 11 \equiv 2 \pmod{3} \end{cases} $$

Now, we compute the Legendre symbol for $ b = 11 $:

\[ \left( \frac{11}{15} \right) = \left( \frac{11}{3} \right) \cdot \left( \frac{11}{5} \right) \]

Since $ 11 \equiv 2 \pmod{3} $ and 2 is not a square modulo 3, we get $\left( \frac{11}{3} \right) = -1 $.

\[ \left( \frac{11}{15} \right) = (-1) \cdot \left( \frac{11}{5} \right) \]

Since $ 11 \equiv 1 \pmod{5} $ and 1 is always a quadratic residue modulo any number, we have $ \left( \frac{11}{5} \right) = 1 $.

\[ \left( \frac{11}{15} \right) = (-1) \cdot 1 = -1 \]

Thus, we have confirmed that $ b = 11 $ meets the required condition: it is coprime to $ 15 $ and is a quadratic non-residue modulo $ 15 $.

Verification. To verify this, we compute all quadratic residues modulo $ n=15 $. The quadratic residues modulo $ 15 $ are $ 0, 1, 4, 6, 9, 10 $. All other numbers—$ 2,3,5,7,8,11 $—are non-residues, including 11.

$0^2 = 0 \equiv 0 \pmod{15}$
$1^2 = 1 \equiv 1 \pmod{15}$
$2^2 = 4 \equiv 4 \pmod{15}$
$3^2 = 9 \equiv 9 \pmod{15}$
$4^2 = 16 \equiv 1 \pmod{15}$
$5^2 = 25 \equiv 10 \pmod{15}$
$6^2 = 36 \equiv 6 \pmod{15}$
$7^2 = 49 \equiv 4 \pmod{15}$
$8^2 = 64 \equiv 4 \pmod{15}$
$9^2 = 81 \equiv 6 \pmod{15}$
$10^2 = 100 \equiv 10 \pmod{15}$
$11^2 = 121 \equiv 1 \pmod{15}$
$12^2 = 144 \equiv 9 \pmod{15}$
$13^2 = 169 \equiv 4 \pmod{15}$
$14^2 = 196 \equiv 1 \pmod{15}$

Proof

To establish this result, we consider two cases: first, when $ n $ is prime, and second, when $ n $ is composite.

1] Case: $ n $ is prime

If $ n $ is a prime number, we already know that there exist values that are not quadratic residues modulo $ n $. That is, there are integers $ b $ such that $ \left( \frac{b}{n} \right) = -1 $.

For a prime $ n $, exactly half of the elements in $ \mathbb{Z}_p^\times $ are quadratic residues, while the remaining half are quadratic non-residues.

In other words, there are precisely $ \frac{p-1}{2} $ quadratic residues and an equal number of non-residues.

Thus, the existence of at least one quadratic non-residue is guaranteed.

For example, if $ n = 7 $, the quadratic residues modulo 7 are {1, 2, 4}, while the non-residues are {3, 5, 6}. The number $ b = 3 $ is not a quadratic residue modulo 7 because there is no $ x $ such that $ x^2 \equiv 3 \pmod{7} $. Below is the verification:

$$ \begin{aligned} 0^2 &\equiv 0 \pmod{7} \\ 1^2 &\equiv 1 \pmod{7} \\ 2^2 &\equiv 4 \pmod{7} \\ 3^2 &\equiv 9 \equiv 2 \pmod{7} \\ 4^2 &\equiv 16 \equiv 2 \pmod{7} \\ 5^2 &\equiv 25 \equiv 4 \pmod{7} \\ 6^2 &\equiv 36 \equiv 1 \pmod{7} \end{aligned} $$

2] Case: $ n $ is composite

If $ n $ is composite, we consider a prime factor $ p $ that appears with an odd exponent in the prime factorization of $ n $.

We express $ n $ as $ n = p^e m $, where $ e $ is odd.

Now, we choose $ t $ to be a number that is not a quadratic residue modulo $ p $.

By the Chinese Remainder Theorem, we can construct an integer $ b $ that satisfies the following system of congruences:

\[ \begin{cases} b \equiv t \pmod{p} \\ \\ b \equiv 1 \pmod{m} \end{cases} \]

This ensures that $ b \equiv t \pmod{p} $, meaning $ b $ is not a quadratic residue modulo $ p $.

At the same time, since $ b \equiv 1 \pmod{m} $, it is a quadratic residue modulo $ m $.

Now, let’s compute the Legendre symbol:

Since $ n = p^e m $, we have:

\[ \left( \frac{b}{n} \right) = \left( \frac{b}{p} \right)^e \cdot \left( \frac{b}{m} \right) \]

We already know that $ b \equiv t \pmod{p} $, and since $ t $ is not a quadratic residue, we have $ \left( \frac{b}{p} \right) = -1 $.

Furthermore, since $ b \equiv 1 \pmod{m} $, we get $ \left( \frac{b}{m} \right) = 1 $.

Thus, we obtain:

\[ \left( \frac{b}{n} \right) = (-1)^e \cdot 1 \]

Since $ e $ is odd, and raising $-1$ to an odd power gives $-1$, we conclude that:

\[ \left( \frac{b}{n} \right) = -1 \]

This proves that, in both cases, there always exists at least one base $ b $ that is a quadratic non-residue modulo $ n $.

And that completes the proof.