Skip to main content

Chapter 9 Quadratic Residues

Consider the quadratic congruence

\begin{equation*} ax^2 + bx + c \equiv 0\pmod{p} \end{equation*}

where \(p\) is an odd prime, and \(a \not\equiv 0\pmod{p},\) so \(\gcd(a, p) = 1.\) Since \(p\) is an odd prime, \(\gcd(4a, p) = 1,\) so we can multiply each side by \(4a\) to get

\begin{equation*} 4a(ax^2 + bx + c) \equiv 0\pmod{p}. \end{equation*}

Now

\begin{equation*} 4a(ax^2 + bx + c) = (2ax + b)^2-(b^2-4ac)\equiv 0 \pmod{p} \end{equation*}

so that our congruence can be written

\begin{equation*} (2ax + b)^2 \equiv (b^2-4ac) \pmod{p}. \end{equation*}

So we are interested in congruences of the form

\begin{equation*} x^2 \equiv a\pmod{p}. \end{equation*}

If \(y\) is a solution, then \(p-y\) is also a solution, so the congruence has two solutions or no solutions.

Definition 9.0.1.

Let \(p\) be an odd prime, and \(\gcd(a, p) = 1.\) If the quadratic congruence \(x^2\equiv a\pmod{p}\) has a solution, then \(a\) is called a quadratic residue of \(p.\) If not, then \(a\) is called a quadratic nonresidue of \(p.\)

Consider \(p = 7.\) Then

\begin{align*} 1^2 \amp \equiv 1 \pmod{7} \hspace{10mm} 2^2 \equiv 4 \pmod{7}\\ 3^2 \amp \equiv 2 \pmod{7} \hspace{10mm} 4^2 \equiv 2 \pmod{7}\\ 5^2 \amp \equiv 4 \pmod{7} \hspace{10mm} 6^2 \equiv 1 \pmod{7} \end{align*}

so that \(1,2,4\) are quadratic residues of \(7,\) and \(3,5,6\) are quadratic nonresidues of \(7.\)

Suppose that \(a\) is a quadratic residue of \(p,\) so that \(x^2 \equiv a\pmod{p}\) has a solution, say \(y.\) Since \(\gcd(a, p) = 1,\) we have \(\gcd(y, p) = 1,\) and so using Fermat's Little Theorem we have

\begin{equation*} a^{(p-1)/2}\equiv (y^2)^{(p-1)/2} = y^{p-1} \equiv 1\pmod{p}. \end{equation*}

Conversely suppose that \(a^{(p-1)/2} \equiv 1\pmod{p}\) and let \(r\) be a primitive root of \(p.\) Then \(a \equiv r^k\pmod{p}\) for some \(k\) with \(1\leq k\leq p-1.\) So

\begin{equation*} r^{k(p-1)/2} \equiv a^{(p-1)/2} \equiv 1\pmod{p}. \end{equation*}

But the order of \(r\) must divide \(k(p-1)/2;\) that is, \(p-1\vert k(p- 1)/2,\) so that \(k\) must be even, say \(k = 2n\) for some \(n.\) Thus

\begin{equation*} (r^n)^2 \equiv r^{2n} \equiv r^k \equiv a\pmod{p} \end{equation*}

so that \(r^n\) is a solution to \(x^2 \equiv a\pmod{p}\) and \(a\) is a quadratic residue of \(p.\)

Let \(\gcd(a, p) = 1.\) Then by Fermat's Little Theorem we have that

\begin{equation*} a^{p-1}-1 = (a^{(p-1)/2}-1)(a^{(p-1)/2} + 1) \equiv 0\pmod{p}, \end{equation*}

so that either

\begin{equation*} a^{\frac{(p-1)}{2}} \equiv 1 \pmod{p} \hspace{5mm} \mathrm{or} \hspace{5mm} a^{\frac{(p-1)}{2}} \equiv -1 \pmod{p}. \end{equation*}

If the first congruence holds, then \(a\) is a quadratic residue of \(p.\) If the first does not hold, then the second must, and \(a\) is a quadratic nonresidue of \(p.\)

Consider \(p = 13.\) Now

\begin{equation*} 2^{(13-1)/2} = 2^6 = 64 \equiv 12 \equiv -1\pmod{13}, \end{equation*}

and

\begin{equation*} 3^{(13-1)/2} = 3^6 = (27)^2 \equiv 1\pmod{13}, \end{equation*}

so that \(2\) is a quadratic nonresidue of \(13\) and \(3\) is a quadratic residue of \(13.\)