1 The Law of Quadratic Reciprocity 133Letgbe a primitive root modp. Then the integers 1,g,...,gp−^2 modpare just a
rearrangement of the integers 1, 2 ,...,p−1. The permutation
πg:x→gx(modp)fixes 0 and cyclically permutes the remaining elements 1,g,...,gp−^2. Since the num-
ber of inversions of order isp−2, it follows that(g/p)=−1. For any integeranot
divisible bypthere is a uniquek∈{ 0 , 1 ,...,p− 2 }such thata≡gkmodp. Hence
(a/p)=(gk/p)=(g/p)k=(− 1 )k.Thus(a/p)=1 if and only ifkis even and thena≡x^2 modpwithx=gk/^2.
This proves the first statement of the proposition. Since exactly half the integers in
the set{ 0 , 1 ,...,p− 2 }are even, it also proves again (cf. Proposition II.28) the second
statement.
The law of quadratic reciprocity can now be established without difficulty:Theorem 7Let p and q be distinct odd primes. Then the quadratic natures of pmodq
and qmodparethesameif p≡ 1 or q≡1mod4, but different if p≡q≡3mod4.
Proof The result follows at once from Proposition 6 since, by Proposition 2(i),
if eitherp≡1orq≡1 mod 4 then(p/q)=(q/p),butifp≡q≡3 mod 4 then
(p/q)=−(q/p).
Legendre (1798)defined(a/p)=1or−1 according asawas a quadratic residue
or nonresidue ofp, and Jacobi (1837) extended this definition to(a/n)for any odd
positive integernrelatively prime toaby setting
(a/n)=∏
p(a/p),wherepruns through the prime divisors ofn, each occurring as often as its multi-
plicity. Propositions 5 and 6 show that these definitions of Legendre and Jacobi are
equivalent to the definition adopted here. The relations(− 1 /p)=(− 1 )(p−^1 )/^2 and
( 2 /p)=(− 1 )(p
(^2) − 1 )/ 8
for odd primespare often called thefirst and second supple-
mentsto the law of quadratic reciprocity.
It should be noted that, if the congruencex^2 ≡amodnis soluble then(a/n)=1,
but the converse need not hold whennis not prime. For example, ifn=21 and
a=5 then the congruencex^2 ≡5 mod 21 is insoluble, since both the congruences
x^2 ≡5 mod 3 andx^2 ≡5 mod 7 are insoluble, but
(
5
21
)
=
(
5
3
)(
5
7
)
=(− 1 )^2 = 1.
The Jacobi symbol finds an interesting application in the proof of the following
result:
Proposition 8If a is an integer which is not a perfect square, then there exist infinitely
many primes p not dividing a for which(a/p)=− 1.