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.

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.