Quadratic Residues and Reciprocity - Applications

The theory of quadratic residues has far-reaching applications in solving Diophantine equations, primality testing, and understanding the factorization of primes in algebraic number fields. These applications demonstrate the power of quadratic reciprocity.

TheoremPrimes of the Form $x^2 + ny^2$

Quadratic reciprocity determines which primes can be represented as $x^2 + ny^2$ for various $n$ . For example:

$x^2 + y^2$ : An odd prime $p$ can be written as $x^2 + y^2$ if and only if $p \equiv 1 \pmod{4}$ .
$x^2 + 2y^2$ : A prime $p > 2$ can be written as $x^2 + 2y^2$ if and only if $p \equiv 1, 3 \pmod{8}$ .
$x^2 + 3y^2$ : A prime $p > 3$ can be written as $x^2 + 3y^2$ if and only if $p \equiv 1 \pmod{3}$ .

These results connect quadratic forms with prime factorization in quadratic number fields, a central theme in algebraic number theory.

ExamplePrimes as Sums of Two Squares

The theorem predicts:

$5 = 1^2 + 2^2$ (since $5 \equiv 1 \pmod{4}$ )
$13 = 2^2 + 3^2$ (since $13 \equiv 1 \pmod{4}$ )
$17 = 1^2 + 4^2$ (since $17 \equiv 1 \pmod{4}$ )

But $7$ and $11$ (both $\equiv 3 \pmod{4}$ ) cannot be written as sums of two squares.

This is connected to the factorization in $\mathbb{Z}[i]$ : primes $p \equiv 1 \pmod{4}$ split in $\mathbb{Z}[i]$ , while primes $p \equiv 3 \pmod{4}$ remain prime.

TheoremTonelli-Shanks Algorithm

Given a prime $p$ and a quadratic residue $a$ modulo $p$ (i.e., $\left(\frac{a}{p}\right) = 1$ ), the Tonelli-Shanks algorithm efficiently computes a solution to $x^2 \equiv a \pmod{p}$ in expected polynomial time.

The algorithm runs in $O(\log^2 p \cdot \log \log p)$ time when implemented with fast arithmetic.

This algorithm is crucial for elliptic curve cryptography, where we frequently need to extract square roots modulo large primes.

ExampleSquare Root Extraction

Find $x$ such that $x^2 \equiv 5 \pmod{11}$ .

We know $\left(\frac{5}{11}\right) = 1$ , so a solution exists. For $p \equiv 3 \pmod{4}$ (like $p = 11$ ), the solution is particularly simple: $x \equiv a^{(p+1)/4} \equiv 5^{(11+1)/4} = 5^3 = 125 \equiv 4 \pmod{11}$

Verification: $4^2 = 16 \equiv 5 \pmod{11}$ . ✓

The other solution is $-4 \equiv 7 \pmod{11}$ .

TheoremQuadratic Reciprocity and Prime Factorization

Let $p$ be an odd prime and consider the quadratic field $\mathbb{Q}(\sqrt{d})$ where $d$ is squarefree. The prime $p$ splits, remains prime, or ramifies in $\mathbb{Z}[\sqrt{d}]$ according to:

Splits: $p$ factors as $p = \pi \bar{\pi}$ if $\left(\frac{d}{p}\right) = 1$
Inert: $p$ remains prime if $\left(\frac{d}{p}\right) = -1$
Ramifies: $p$ divides $d$ if $\left(\frac{d}{p}\right) = 0$

This connection between quadratic residues and prime factorization in number fields is fundamental to algebraic number theory.

ExampleFactorization in $\mathbb{Z}[\sqrt{-5}]$

In $\mathbb{Z}[\sqrt{-5}]$ , consider the prime $3$ :

We check $\left(\frac{-5}{3}\right) = \left(\frac{-1}{3}\right)\left(\frac{5}{3}\right) = (-1)\left(\frac{2}{3}\right) = (-1)(-1) = 1$ .

So $3$ splits: $3 = (2 + \sqrt{-5})(2 - \sqrt{-5})$ in $\mathbb{Z}[\sqrt{-5}]$ .

For $7$ : $\left(\frac{-5}{7}\right) = \left(\frac{2}{7}\right) = 1$ , so $7$ also splits.

For $13$ : $\left(\frac{-5}{13}\right) = \left(\frac{8}{13}\right) = \left(\frac{2^3}{13}\right) = 1$ , so $13$ splits as well.

Remark

The Solovay-Strassen primality test uses the Jacobi symbol: for odd composite $n$ , at least half of all bases $a$ with $\gcd(a, n) = 1$ satisfy: $a^{(n-1)/2} \not\equiv \left(\frac{a}{n}\right) \pmod{n}$

This provides a probabilistic primality test running in polynomial time.

These applications show how quadratic residues connect pure number theory with computational algorithms and algebraic structures.