Quadratic Residues and Sound Diffusers

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.

OldTrout, Going Postal

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 moduloto 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\}\).

OldTrout, Going Postal

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\)