# 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.

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\}$$.

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$$