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\).
Suppose that the considered congruence has a
solution \(x_1\). Then so clearly is \(x_2=-x_1\). There are no other
solutions modulo \(p\), because \(x^2\equiv a\equiv x_1^2\) (mod \(p\))
implies \(x\equiv\pm
x_1.\)
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 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'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 statement is trivial for \(p\mid a\). From now
on we assume that \(p\nmid a\).
Let \(g\) be a primitive root modulo \(p\). Then the numbers \(g^i\), \(i=0,1,
\dots,p-2\) form a reduced system of residues modulo \(p\). We observe
that \((g^i)^{p\prime}= g^{ip\prime}\equiv1\) if and only if \(p-1\mid ip\prime\), or
equivalently, \(2\mid i\).
On the other hand, \(g^i\) is a quadratic residue modulo \(p\) if and only
if there exists \(j\in\{0,1,\dots,p-2\}\) such that \((g^j)^2\equiv g^i\)
(mod \(p\)), which is equivalent to \(2j\equiv i\) (mod \(p-1\)) .
The last congruence is solvable if and only if \(2\mid i\), that is,
exactly when \((g^i)^{p\prime}\equiv1\) (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\).
Consider the smallest positive quadratic
nonresidue \(a\) modulo \(p\) and let \( b=\left[\frac pa\right]+1\).
Since \(0 < ab-p < a\), \(ab-p\) must be a quadratic residue. Therefore
\[1=\left(\frac{ab-p}p\right)=\left(\frac ap\right)\left(\frac ap
\right)=-\left(\frac bp\right).\] Thus \(b\) is a quadratic nonresidue
and hence \( a\leq b < \frac pa+1\), which implies the statement.
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\)).
Multiplying the congruences \(i\equiv-(p-i)\)
(mod \(p\)) for \(i=1,2,\dots,p\prime\) yields \((p\prime)!\equiv(-1)^{p\prime}
(p\prime+1)\cdots(p-2)(p-1)\). Note that \(p\prime\) is even by the condition of the
problem. We now have \[x^2=(p\prime)!^2\equiv(-1)^{p\prime}p\prime\cdot
(p\prime+1)\cdots(p-2)(p-1)=(-1)^{p\prime}(p-1)!\equiv(-1)^{p\prime+1}=-1\mbox{
(mod }p)\] by Wilson's theorem.
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\)).
Denote \(N=ax^2+bxy+cy^2\). Since \(4aN=(2ax+by)^2-
Dy^2\), we have \[(2ax+by)^2\equiv Dy^2\;\;\mbox{(mod }p).\]
Furthermore, \(y\) is not divisible by \(p\); otherwise so would be
\(2ax+by\) and therefore \(x\) itself, contradicting the assumption.
There is an integer \(y_1\) such that \(yy_1\equiv1\) (mod \(p\)).
Multiplying the above congruence by \(y_1^2\) gives us \((2axy_1+byy_1)^2
\equiv D(yy_1)^2\equiv D\) (mod \(p\)), implying the statement.
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\).
(a) Suppose the contrary, that \(p_1,p_2,\dots,
p_n\) are all such numbers. Then by Theorem 5, all prime divisors of
\(N=(2p_1p_2\cdots p_n)^2+1\) are of the form \(4k+1\). However, \(N\) is not
divisible by any of \(p_1,p_2,\dots,p_n\), which is impossible.
Part (b) is similar to (a), with number \(N=5(2p_1p_2\cdots p_n)^2-1\)
being considered instead.
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\).
We observe that \[n^4-n^2+1=(n^2-1)^2+n^2
\hspace{5mm}\mbox{i}\hspace{5mm}n^4-n^2+1=(n^2+1)^2-3n^2.\]
In view of theorems 5, 6, and 10, the first equality gives us
\(p\equiv1\) (mod 4), whereas the other one gives us
\(p\equiv\pm1\) (mod 12). These two congruences together yield
\(p\equiv1\) (mod 12).
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].\]
Note that 2003 is prime.
It follows from Euler's criterion and Theorem
10 that \(2^{1001}\equiv\left(\frac2{2003} \right)=-1\)
(mod \(2003\)). Therefore \(2003\mid 2^i(2^{1001}+1)=2^{1001+i}+2^i\);
since \(2^i\) and \(2^{1001+i}\) are not multiples of \(2003\), we conclude
that \[\left[\frac{2^i}{2003}\right]+\left[\frac{2^{1001+i}}{2003}
\right]=\frac{2^i+2^{1001+i}}{2003}-1.\] Summing up these equalities
for \(i=0,1,\dots,1000\) we obtain that the desired sum equals
\[\frac{1+2+2^2+\cdots+2^{2001}}{2003}-1001=
\frac{2^{2002}-1}{2003}-1001.\]
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\).
Define \( S(p,q)=\sum_{k=1}^{q\prime}\left[
\frac{kp}q\right]\). We start by proving the following auxiliary
statement.
Lemma. \(S(p,q)+S(q,p)=p\prime q\prime\).
Proof of the Lemma.
Given \(k\in\mathbb{N}\), we note that \(\left[
\frac{kp}q\right]\) is the number of integer points \((k,l)\) in the
coordinate plane with \(0 < l < kp/q\), i.e. such that \(0 < ql < kp\). It follows
that the sum \(S(p,q)\) equals the number of integer points \((k,l)\) with
\(0 < k < p\prime\) and \(0 < ql < kp\). Thus \(S(p,q)\) is exactly the number of points
with positive integer coordinates in the interior or on the boundary of
the rectangle \(ABCD\) that lie {\it below} the line \(AE\), where
\(A(0,0)\), \(B(p\prime,0)\), \(C(p\prime,q\prime)\), \(D(0,q\prime)\), \(E(p,q)\).
Analogously, \(S(q,p)\) is exactly the number of points with positive
integer coordinates in the interior or on the boundary of the rectangle
\(ABCD\) that lie {\it above} the line \(AE\). Since there are \(p\prime q\prime\)
integer points in total in this rectangle, none of which is on the
line \(AE\), it follows that \(S(p,q)+S(q,p)=p\prime q\prime\). \(\triangledown\)
We now return to the proof of the theorem. We have \[S(p+q,q)-S(p,q)=1+
2+\dots+p\prime=\frac{p^2-1}8.\] Since Theorem 9 is equivalent to \(
\left(\frac2p\right)=(-1)^{\frac{p^2-1}8}\), Gauss' lemma gives us
\[\left(\frac2q\right)\left(\frac pq\right)=\left(\frac{2p}q\right)
=\left(\frac{2(p+q)}q\right)=\left(\frac{\frac{p+q}2}q\right)=
(-1)^{S(p+q,q)}=\left(\frac2q\right)(-1)^{S(p,q)},\] hence \(
\left(\frac pq\right)=(-1)^{S(p,q)}\). Analogously, \(\left(\frac
qp\right)=(-1)^{S(q,p)}\). Multiplying the last two inequalities and
using the lemma yields the desired equality.
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.
Suppose that \(a\) is not a square. We may assume
w.l.o.g. (why?) that \(a\) is square-free.
Suppose that \(a > 0\). Then \(a=p_1p_2\cdots p_k\) for some primes \(p_1,
\dots,p_k\). For every prime number \(p\) it holds that
\[\left(\frac ap\right)=\prod_{i=1}^k\left(\frac{p_i}p\right)
\quad\mbox{and}\quad\left(\frac{p_i}p\right)=
(-1)^{p_i\prime p\prime}\left(\frac p{p_i}\right).\quad\quad\quad\quad\quad(1)\] If \(a=2\), it is
enough to choose \(p=5\). Otherwise \(a\) has an odd prime divisor, say
\(p_k\). We choose a prime number \(p\) such that \(p\equiv1\) (mod 8),
\(p\equiv 1\) (mod \(p_i\)) for \(i=1,2,\dots,k-1\), and \(p\equiv a\)
(mod \(p_k\)), where \(a\) is an arbitrary quadratic nonresidue
modulo \(p_k\). Such prime number \(p\) exists according to the Dirichlet
theorem on primes in an arithmetic progression. Then it follows from
(1) that \(p_1,\dots,p_{k-1}\) are quadratic residues modulo \(p\), but
\(p_k\) is not. Therefore \(a\) is a quadratic nonresidue modulo \(p\).
The proof in the case \(a < 0\) is similar and is left to the reader.