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