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

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

This text is mainly concerned with quadratic residues.

Theorem 1 Given a prime $$p$$ and an integer $$a$$, the equation $$x^2\equiv a$$ has zero, one, or two solutions modulo $$p$$.

As a consequence of the above simple statement we obtain:

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 2Since 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$$.

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:

Theorem 3 (Euler's Criterion) $$a^{p\prime}\equiv\left(\frac ap\right)$$ (mod $$p$$).

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

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 5For every prime number $$p > 2$$, $$\left(\frac{-1}p\right)=(-1)^{\frac{p-1}2}$$.

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

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

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.

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

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:

Theorem 7 $$\left(\frac ap\right)= \epsilon_1\epsilon_2\cdots\epsilon_{p\prime}$$.

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.

Theorem 8 (Gauss' Lemma) $$\left( \frac ap\right)=(-1)^S$$, where $$S=\sum_{k=1}^{p\prime} \left[\frac{2ka}p\right]$$.

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

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

The following statements can be similarly shown.

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

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.

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

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

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.