Quadratic congruences (Table of contents)
# Quadratic Congruences with Prime Moduli

**Definition** Let \(m,n\) and \(a\) be integers, \(m > 1\), \(n\geq1\) and
\((a,m)=1\). We say that \(a\) is a * residue of* \(n\)-*th degree* modulo
\(m\) if congruence \(x^n\equiv a\) (mod \(m\)) has an integer
solution; else \(a\) is a * nonresidue of \(n\)-th degree*.
**Theorem 1** Given a prime \(p\) and an
integer \(a\), the equation \(x^2\equiv a\) has zero, one, or two solutions
modulo \(p\).
**Theorem 2**
For every odd positive
integer \(p\), among the numbers \(1,2,\dots,p-1\) there are exactly
\(\frac{p-1}2\) quadratic residues (and as many quadratic nonresidues).
**Definition**
Given a prime number \(p\) and an integer \(a\), *
Legendre's symbol* \(\left(\frac ap\right)\) is defined as
\[\left(\frac ap\right)=\left\{\begin{array}{cl}1,&\mbox{if }
p\nmid a\mbox{ and } a \mbox{ is a quadratic residue (mod }p);\newline -1,
&\mbox{if }p\nmid a \mbox{ and }a \mbox{ is a quadratic nonresidue (mod }
p);\newline 0,&\mbox{if }p\mid a.\end{array}\right.\]
**Example 1**
Obviously, \(\left(\frac{x^2}p\right)
=1\) for each prime \(p\) and integer \(x\), \(p\nmid x\).
**Example 2**Since 2 is a quadratic residue modulo 7
(\(3^2\equiv 2\)), and 3 is not, we have \(\left(\frac27\right)=1\) and
\(\left(\frac37\right)=-1\).
**Theorem 3 (Euler's Criterion)**
\(a^{p\prime}\equiv\left(\frac ap\right)\) (mod \(p\)).
**Theorem 4** Legendre's symbol
is multiplicative, i.e.
\(\left(\frac{ab}p\right)=\left(\frac ap\right)
\left(\frac bp\right)\)
for all integers \(a,b\) and prime number \(p > 2\).
**Problem 1**
There exists a natural number \(a < \sqrt p+1\)
that is a quadratic nonresidue modulo \(p\).
**Theorem 5**For every prime number
\(p > 2\), \(
\left(\frac{-1}p\right)=(-1)^{\frac{p-1}2}\).
**Problem 2**
If \(p\) is a prime of the form \(4k+1\), prove
that \(x=(p\prime)!\) is a solution of the congruence \(x^2+1\equiv0\)
(mod \(p\)).
**Theorem 6** Let \(x,y\) be coprime integers and \(a,b,c\) be
arbitrary integers. If \(p\) is an odd prime divisor of number
\(ax^2+bxy+cy^2\) which doesn't divide \(abc\), then \[D=b^2-4ac\] is a
quadratic residue modulo \(p\).

In particular, if \(p\mid x^2-Dy^2\) and \((x,y)=1\), then \(D\) is a quadratic residue (mod \(p\)).
**Theorem 7** \(\left(\frac ap\right)=
\epsilon_1\epsilon_2\cdots\epsilon_{p\prime}\).
**Theorem 8 (Gauss' Lemma)**
\(\left(
\frac ap\right)=(-1)^S\), where \( S=\sum_{k=1}^{p\prime}
\left[\frac{2ka}p\right]\).
**Theorem 9**\(\left(\frac2p\right)=(-1)^{\left[
\frac{p+1}4\right]}\).

In other words, 2 is a quadratic residue modulo a prime \(p > 2\) if and only if \(p\equiv\pm1\) (mod 8).
**Theorem 10**
(a)-2 is a quadratic
residue modulo \(p\) if and only if \(p\equiv1\) or \(p\equiv 3\)
(mod 8);

(b) -3 is a quadratic residue modulo \(p\) if and only if \(p\equiv1\) (mod 6);

(c) 3 je quadratic residue modulo \(p\) if and only if \(p\equiv\pm1\) (mod 12);

(d) 5 is a quadratic residue modulo \(p\) if and only if \(p\equiv\pm1\) (mod 10).
**Problem 3**
Show that there exist infinitely many prime
numbers of the form (a) \(4k+1\); (b) \(10k+9\).
**Problem 4**
Prove that for \(n\in\mathbb{N}\) every prime
divisor \(p\) of number \(n^4-n^2+1\) is of the form \(12k+1\).
**Problem 5**
Evaluate \[\left[\frac1{2003}\right]
+\left[\frac{2}{2003}\right]+\left[\frac{2^2}{2003}\right]+\cdots+
\left[\frac{2^{2001}}{2003}\right].\]
**Theorem 11 (Gauss' Reciprocity Law)** For any
different odd primes \(p\) and \(q\),
\[\left(\frac pq\right)\left(\frac qp\right)=(-1)^{p\prime q\prime},\] where
\(p\prime=\frac{p-1}2\) and \(q\prime=\frac{q-1}2\).
**Example 3**
\(\left(\frac{814}{2003}\right)=
\left(\frac{2}{2003}\right)\left(\frac{11}{2003}\right)
\left(\frac{37}{2003}\right)=-\left(\frac{11}{2003}\right)
\left(\frac{37}{2003}\right)\).

Furthermore, the Reciprocity Law gives us \[\left(\frac{11}{2003}\right)=-\left(\frac{2003}{11}\right)= \left(\frac{1}{11}\right)=1\quad\mbox{and}\quad\left(\frac{37}{2003} \right)=\left(\frac{2003}{37}\right)=\left(\frac{5}{37}\right)= \left(\frac{37}{5}\right)=-1.\] Thus \(\left(\frac{814}{2003}\right)= 1\), i.e. \(814\) is a quadratic residue modulo \(2003\).
**Problem 6**
Prove that an integer \(a\) is a quadratic
residue modulo every prime number if and only if \(a\) is a perfect
square.

Specifically, for \(n=2,3,4\) the residues are called quadratic, cubic, biquadratic, respectively.

This text is mainly concerned with quadratic residues.

As a consequence of the above simple statement we obtain:

From now on, unless noted otherwise, \(p\) is always an odd prime and \(a\) an integer. We also denote \(p\prime=\frac{p-1}2\).

Clearly, \(a\) is a quadratic residue modulo \(p\) if and only if so is \(a+kp\) for some integer \(k\). Thus we may regard Legendre's symbol as a map from the residue classes modulo \(p\) to the set \(\{-1,0,1\}\).

Fermat's theorem asserts that \(a^{p-1}\equiv1\) (mod \(p\)), which implies \( a^{p\prime}\equiv\pm1\) (mod \(p\)). More precisely, the following statement holds:

The following important properties of Legendre's symbol follow directly from Euler's criterion.

In other words, the congruence \(x^2\equiv-1\) modulo a prime \(p\) is solvable if and only if \(p=2\) or \(p\equiv1\) (mod 4).

One can conclude from Problem 1 that every prime factor of number \(x^2+y^2\) (where \(x,y\in\mathbb{N}\) are coprime) is either of the form \(4k+1\), \(k\in\mathbb{N}\), or equal to 2. This conclusion can in fact be generalized.

In particular, if \(p\mid x^2-Dy^2\) and \((x,y)=1\), then \(D\) is a quadratic residue (mod \(p\)).

For an integer \(a\), \(p\nmid a\) and \(k=1,2,\dots,p\prime\) there is a unique \(r_k\in\{-p\prime,\dots,-2,-1,1,2,\dots,p\prime\}\) such that \(ka\equiv r_k\) (mod \(p\)). Moreover, no two of the \(r_k\) 's can be equal in absolute value; hence \(|r_1|,|r_2|,\dots,|r_{p\prime}|\) is in fact a permutation of \(\{1,2,\dots,p\prime\}\). Then \[a^{p\prime}=\frac{a\cdot2a \cdot\dots\cdot p\prime a}{1\cdot2\cdot\dots\cdot p\prime}\equiv \frac{r_1r_2\dots r_{p\prime}}{1\cdot2\cdot\dots\cdot p\prime}.\] Now, setting \(r_k=\epsilon_k|r_k|\) for \(k=1,\dots,p\prime\), where \(\epsilon_k=\pm1\), and applying Euler's criterion we obtain:

Observe that \(r_k=-1\) if and only if the remainder of \(ka\) upon division by \(p\) is greater than \(p\prime\), i.e. if and only if \(\left[ \frac{2ka}p\right]=2\left[\frac{ka}p\right]+1\). Therefore, \( r_k= (-1)^{\left[\frac{2ka}p\right]}\). Now Theorem 7 implies the following statement.

Gauss' lemma enables us to easily compute the value of Legendre's symbol \(\left(\frac ap\right)\) for small \(a\) or small \(p\). If, for instance, \(a=2\), we have \(\left(\frac2p\right)=(-1)^S\), where \( S=\sum_{k=1}^{p\prime}\left[\frac{4k}p\right]\). Exactly \(\left[ \frac12p\prime\right]\) summands in this sum are equal to 0, while the remaining \( p\prime-\left[\frac12p\prime\right]\) are equal to 1. Therefore \( S=p\prime-\left[\frac12p\prime\right]=\left[\frac{p+1}4\right]\), which is even for \(p\equiv\pm1\) and odd for \(p\equiv\pm3\) (mod 8). We have proven the following

In other words, 2 is a quadratic residue modulo a prime \(p > 2\) if and only if \(p\equiv\pm1\) (mod 8).

The following statements can be similarly shown.

(b) -3 is a quadratic residue modulo \(p\) if and only if \(p\equiv1\) (mod 6);

(c) 3 je quadratic residue modulo \(p\) if and only if \(p\equiv\pm1\) (mod 12);

(d) 5 is a quadratic residue modulo \(p\) if and only if \(p\equiv\pm1\) (mod 10).

The theory we have presented so far doesn't really facilitate the job if we need to find out whether, say, \(814\) is a quadratic residue modulo \(2003\). That will be done by the following theorem, which makes such a verification possible with the amount of work comparable to that of the Euclidean algorithm.

Let us now do the example mentioned before the Reciprocity Law.

Furthermore, the Reciprocity Law gives us \[\left(\frac{11}{2003}\right)=-\left(\frac{2003}{11}\right)= \left(\frac{1}{11}\right)=1\quad\mbox{and}\quad\left(\frac{37}{2003} \right)=\left(\frac{2003}{37}\right)=\left(\frac{5}{37}\right)= \left(\frac{37}{5}\right)=-1.\] Thus \(\left(\frac{814}{2003}\right)= 1\), i.e. \(814\) is a quadratic residue modulo \(2003\).