We touched on quadratic residues when discussing Pythagorean triples. We relied upon the quadratic residues and non-residues in modulo \(4\) for our proof that \(x\) and \(y\) took opposite parities.

These residues have important results in encryption, integer factorisation and sound diffusion.

Definition of quadratic residues :

Let :

\(p\) be an odd prime and \(a \not \equiv 0 \pmod p\).

If the congruence \(x^2 \equiv a \pmod p\) has a solution, then \(a\) is said to be *a quadratic residue* of \(p\).

Otherwise, \(a\) is *a quadratic non-residue* of \(p\).

We are more interested in finding when a quadratic congruence has a solution than in solving the quadratic congruence at this point. It leads to Euler’s Criterion, Gauss’ Lemma and the Law of Quadratic Reciprocity.

The quadratic residues of* p :*

For any odd prime *p, *there are \(\frac {p – 1}{2}\) quadratic residues and \(\frac {p – 1}{2}\) quadratic non-residues.

The quadratic residues are congruent modulo* p *to the integers \(1^2, 2^2, 3^2, . . . , \frac {p – 1}{2}\).

They are symmetrical.

In modulo \(5\) the quadratic residues are :

\(1^2 \equiv 1 \pmod 5 \\

2^2 \equiv 4 \pmod 5 \\

3^2 \equiv 4 \pmod 5 \\

4^2 \equiv 1 \pmod 5 \)

Modulo \(7\) gives the set \(\{1, 4, 2, 2, 4, 1\}\).

Modulo \(11\) gives the set \(\{1, 4, 9, 5, 3, 3, 5, 9, 4, 1\}\).

Modulo \(13\) gives the set \(\{1, 4, 9, 3, 12, 10, 10, 12, 3, 9, 4, 1\}\).

Euler’s Criterion :

Let :

\(p\) be an odd prime and \(a \not \equiv 0 \pmod p\).

\(a\) is a quadratic residue of \(p\) if, and only if, \(a^{(p-1)/2} \equiv 1 \pmod p\).

\(a\) is a quadratic non-residue of \(p\) if, and only if, \(a^{(p-1)/2} \equiv -1 \pmod p\).

© OldTrout \(2018\)