Number Theory: An Introduction to Mathematics

5 Congruences 113

Proof Ifais a quadratic residue ofp,thena≡c^2 modpfor some integercand
hence, by Fermat’s little theorem,

a(p−^1 )/^2 ≡cp−^1 ≡1modp.

Since the polynomialt(p−^1 )/^2 −1 has at most(p− 1 )/2 roots in the fieldFp, it follows
that there are at mostr:=(p− 1 )/2 distinct quadratic residues ofp. On the other
hand, no two of the integers 1^2 , 22 ,...,r^2 are congruent modp,sinceu^2 ≡v^2 modp
impliesu≡voru≡−vmodp. Hence there are exactly(p− 1 )/2 distinct quadratic
residues ofpand, ifbis a quadratic nonresidue ofp,thenb(p−^1 )/^2 ≡1modp.Since
bp−^1 ≡1modp,and

bp−^1 − 1 =(b(p−^1 )/^2 − 1 )(b(p−^1 )/^2 + 1 ),

we must haveb(p−^1 )/^2 ≡−1modp.

Corollary 29If p is an odd prime, then− 1 is a quadratic residue of p if p≡1mod4
and a quadratic nonresidue of p if p≡3mod4.

Euler’s criterion may also be used to determine for what primes 2 is a quadratic
residue:

Proposition 30For any odd prime p, 2 is a quadratic residue of p if p≡±1mod8
and a quadratic nonresidue if p≡±3mod8.

Proof LetAdenote the set of all even integersasuch thatp/ 2 <a<p,andletB
denote the set of all even integersbsuch that 0<b<p/2. SinceA∪Bis the set
of all positive even integers less thanp, it has cardinalityr:=(p− 1 )/2. Evidently
a∈Aif and only ifp−ais odd and 0<p−a<p/2. Hence the integers 1, 2 ,...,r
are just the elements ofB, together with the integersp−a(a∈A). If we denote the
cardinality ofAby #A, it follows that

r!=

∏

a∈A

(p−a)

∏

b∈B

b

≡(− 1 )#A

∏

a∈A

a

∏

b∈B

bmodp

=(− 1 )#A 2 rr!

Thus 2r≡(− 1 )#Amodpand hence, by Proposition 28, 2 is a quadratic residue or
nonresidue ofpaccording as #Ais even or odd. But #A=kifp= 4 k+1and
#A=k+1ifp= 4 k+3. The result follows.

We now introduce some simple group-theoretical concepts. LetGbe a finite group
anda∈G. Then there existj,k∈Nwithj<ksuch thataj=ak. Thusak−j=1,
where 1 is the identity element ofG.Theorderofais the least positive integerdsuch
thatad=1.

Lemma 31Let G be a finite group of order n and a an element of G of order d. Then

(i)for any k∈N,ak= 1 if and only if d divides k;