Quadratic Residue

An integer \( a \) is a quadratic residue modulo \( p \) if there exists an integer \( x \) such that: \[x^2 \equiv a \pmod{p}\]If no such \( x \) exists, then \( a \) is not a quadratic residue modulo \( p \).

Simply put, if squaring some integer \( x \) gives a result congruent to \( a \) modulo \( p \), then \( a \) is a quadratic residue under this modulus. Otherwise, it is not.

Therefore, a quadratic residue is a number that has a square root modulo \( p \).

Note: To determine whether a number \( a \) is a quadratic residue modulo \( n \), regardless of whether \( n \) is prime or composite, you can compute all the squares modulo \( n \) and check if \( a \) appears in the list.  

A Practical Example

Let's compute the squares of numbers modulo \( p = 7 \) for each \( x \) from 0 to 6:

• \( 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} \)

So, the quadratic residues modulo \( 7 \) are: \{0, 1, 2, 4\}

Since 3, 5, and 6 are missing from the list, they are not quadratic residues modulo 7.

How to Check If a Number Is a Quadratic Residue Modulo \( p \)

To determine whether \( a \) is a quadratic residue modulo \( n \), follow these steps:

1. Compute all squares \( x^2 \mod n \) for \( x = 0, 1, 2, \dots, n-1 \).
2. Check the results:
   - If \( a \) appears in the list, then \( a \) is a quadratic residue modulo \( n \).
   - If \( a \) does not appear, then \( a \) is not a quadratic residue modulo \( n \).

This approach works well for small values of \( n \), but for larger numbers, it's more efficient to use methods like the Legendre or Jacobi symbols.

Example

Let's check whether \( 2 \) is a quadratic residue modulo \( 15 \).

We compute the squares \( x^2 \mod 15 \) for \( x = 0, 1, \dots, 14 \) and see if \( 2 \) appears.

• \(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}\)

The quadratic residues modulo \( 15 \) are \( 0, 1, 4, 6, 9, 10 \).

Since 2 is not in the list, it means \( 2 \) is not a quadratic residue modulo \( 15 \).

Note: This method is effective for any modulus (whether prime or composite) and is easy to apply when \( n \) is small. However, for larger \( n \), computing all squares quickly becomes impractical. In such cases, alternative methods like the Legendre symbol (for prime \( p \)) or the Jacobi symbol (for composite \( n \)) are preferable.

A Faster Approach

When the modulus is composite (such as \( n = 15 \)), the most efficient method is to use the Jacobi symbol.

The first step is to factorize the modulus:

\[ 15 = 3 \times 5 \]

Next, express the Jacobi symbol as the product of the Legendre symbols of its prime factors:

\[ \left(\frac{2}{15}\right) = \left(\frac{2}{3}\right) \times \left(\frac{2}{5}\right) \]

Now, evaluate each Legendre symbol separately using Euler’s criterion, since the moduli are now prime:

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

When the numerator is 2, as in this case, a special formula simplifies the computation:

\[ \left(\frac{2}{p}\right) = (-1)^{\frac{p^2 - 1}{8}} \]

Modulo 3

\[ \left(\frac{2}{3}\right) = (-1)^{\frac{3^2 - 1}{8}} = (-1)^1 = -1 \]

Modulo 5

\[ \left(\frac{2}{5}\right) = (-1)^{\frac{5^2 - 1}{8}} = (-1)^3 = -1 \]

Final Calculation

Substituting these values into the Jacobi symbol equation:

\[ \left(\frac{2}{15}\right) = \left(\frac{2}{3}\right) \times \left(\frac{2}{5}\right) \]

\[\left(\frac{2}{15}\right) = (-1) \times (-1) = 1 \]

Since the result is 1, this does not necessarily mean that 2 is a quadratic residue modulo 15. It only indicates that it might be.

However, since we have already established that \( a = 2 \) is not a quadratic residue modulo either 3 or 5, we can confidently conclude that 2 is not a quadratic residue modulo 15. This follows from the fact that a number must be a quadratic residue in both prime moduli in order to be a quadratic residue in their product.

Note: If the modulus is \( n = p_1 \cdot p_2 \), where \( p_1 \) and \( p_2 \) are distinct primes, then an integer \( a \) is a quadratic residue modulo \( n \) if and only if it is a quadratic residue modulo both \( p_1 \) and \( p_2 \). Otherwise, it is not a quadratic residue modulo \( n \).

By using this method, we avoid the need to compute all squares modulo 15, arriving at the result much more efficiently.

And so on.