Euler's Criterion
Let \( p \) be an odd prime, and let \( a \) be an integer not divisible by \( p \), meaning \( a \) and \( p \) are coprime (\( \gcd(a, p) = 1 \)). Euler’s criterion states that: \[ \left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod{p} \] where \( \left( \frac{a}{p} \right) \) represents the Legendre symbol.
By computing \( a^{\frac{p-1}{2}} \pmod{p} \), we can determine whether \( a \) is a quadratic residue modulo \( p \).
- If \( \left( \frac{a}{p} \right) = +1 \), then \( a \) is a quadratic residue modulo \( p \).
- If \( \left( \frac{a}{p} \right) = -1 \), then \( a \) is not a quadratic residue modulo \( p \).
Simplified Form for \( a = 2 \)
When checking whether \( a = 2 \) is a quadratic residue, Euler’s criterion simplifies to:
\[ \left( \frac{2}{p} \right) = (-1)^{\frac{p^2 - 1}{8}} \]
This formula determines whether 2 is a quadratic residue modulo an odd prime \( p \).
Why is Euler’s criterion important? It has many applications in mathematics, particularly in number theory, cryptography, and primality testing. One key application is in the Solovay-Strassen primality test.
A Practical Example
Let’s determine whether \( a = 4 \) is a quadratic residue modulo \( p = 7 \).
Using Euler’s criterion:
\[ \left( \frac{4}{7} \right) \equiv 4^{\frac{7-1}{2}} \pmod{7} \]
\[ \left( \frac{4}{7} \right) \equiv 4^3 \pmod{7} \]
\[ \left( \frac{4}{7} \right) \equiv 64 \pmod{7} \]
\[ \left( \frac{4}{7} \right) \equiv 1 \pmod{7} \]
Since the result is \( 1 \), we conclude that \( 4 \) is a quadratic residue modulo \( 7 \). This means there exists an integer \( x = 2 \) such that:
\[ 2^2 \equiv 4 \pmod{7} \]
Verification. To confirm this result, we compute all quadratic residues modulo \( p = 7 \) and check if 4 appears in the list.
- \( 0^2 = 0 \equiv 0 \pmod{7} \)
- \( 1^2 = 1 \equiv 1 \pmod{7} \)
- \( 2^2 = 4 \equiv 4 \pmod{7} \)
- \( 3^2 = 9 \equiv 2 \pmod{7} \)
- \( 4^2 = 16 \equiv 2 \pmod{7} \)
- \( 5^2 = 25 \equiv 4 \pmod{7} \)
- \( 6^2 = 36 \equiv 1 \pmod{7} \)
The quadratic residues modulo \( 7 \) are 0, 1, 2, and 4. This confirms that \( 4 \) is indeed a quadratic residue modulo 7.
Example 2
Now, let's check whether \( a = 3 \) is a quadratic residue modulo \( p = 7 \).
Using Euler’s criterion:
\[ \left( \frac{3}{7} \right) \equiv 3^{\frac{7-1}{2}} \pmod{7} \]
\[ \left( \frac{3}{7} \right) \equiv 3^3 \pmod{7} \]
\[ \left( \frac{3}{7} \right) \equiv 27 \pmod{7} \]
\[ \left( \frac{3}{7} \right) \equiv 6 \pmod{7} \]
Since \( 6 \equiv -1 \pmod{7} \), we obtain:
\[ \left( \frac{3}{7} \right) \equiv -1 \pmod{7} \]
Since the result is \( -1 \), we conclude that \( 3 \) is not a quadratic residue modulo \( 7 \).
Key Properties of Euler’s Criterion
Euler’s criterion has several important properties:
- Multiplicativity of the Legendre Symbol
If \( a \) and \( b \) are integers, then: \[ \left( \frac{a \cdot b}{p} \right) = \left( \frac{a}{p} \right) \cdot \left( \frac{b}{p} \right). \] - Connection to Fermat’s Little Theorem
By Fermat’s Little Theorem: \[ a^{p-1} \equiv 1 \pmod{p} \] Since Euler’s criterion involves the exponent \( \frac{p-1}{2} \), it leverages this property to determine quadratic residues.
And so on.
