# Quadratic Congruences to 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$$\prime$$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);\\ -1, &\mbox{if }p\nmid a \mbox{ and }a \mbox{ is a quadratic nonresidue (mod } p);\\ 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$$.

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$$\prime$$s symbol as a map from the residue classes modulo $$p$$ to the set $$\{-1,0,1\}$$.

Fermat$$\prime$$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$$\prime$$s Criterion)

$$a^{p\prime}\equiv\left(\frac ap\right)$$ (mod $$p$$).

The following important properties of Legendre$$\prime$$s symbol follow directly from Euler$$\prime$$s criterion.

Theorem 4

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

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$$\prime$$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$$ $$\prime$$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$$\prime$$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$$\prime$$ Lemma)

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

Gauss$$\prime$$ lemma enables us to easily compute the value of Legendre$$\prime$$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$$\prime$$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$$\prime$$ 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.

2005-2014 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax
Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us