1 The Law of Quadratic Reciprocity 131and henceα:=vμ−^1 has sign
sgn(α)=(− 1 )(m+n)(m−^1 )(n−^1 )/^2 (m/n)m(n/m)n.Butαis the permutation(mx+ymodn,y)→(x,x+nymodm)and its sign can be
determined directly in the following way.
PutZ={ 0 , 1 ,...,mn− 1 }. By PropositionII.36, for any(x,y)∈Pthere is a
uniquez∈Zsuch that
z≡xmodn, z≡ymodm.Moreover, anyz∈ Zis obtained in this way from a unique(x,y)∈ P.Forany
z∈Z, we will denote byρ(z)the corresponding element ofP. Then the permutation
αcan be written in the formρ(mx+y)→ρ(x+ny).Sinceρis a bijective map,
the sign of the permutationαofPwill be the same as the sign of the permutation
β=ρ−^1 αρ:mx+y→x+nyofZ. An inversion of order forβoccurs when both
mx+y>mx′+y′andx+ny<x′+ny′, i.e. when bothm(x−x′)>y′−yand
x−x′<n(y′−y). But these inequalities implymn(x−x′)>x−x′and hence
x>x′,y′>y.Conversely,ifx>x′,y′>y,then
m(x−x′)≥m>y′−y, n(y′−y)≥n>x−x′.Since the number of(x,y),(x′,y′)∈Pwithx>x′,y<y′ism(m− 1 )/ 2 ·n(n− 1 )/2,
it follows that the sign of the permutationαis(− 1 )mn(m−^1 )(n−^1 )/^4. Comparing this
expression with the expression previously found, we obtain
(m/n)m(n/m)n=(− 1 )(mn+^2 m+^2 n)(m−^1 )(n−^1 )/^4.This simplifies to the first statement of the proposition ifmandnare both odd, and to
the second statement ifmis odd andneven.
Corollary 3For any odd positive integer n,( 2 /n)= 1 or− 1 according as n≡± 1
or±5mod8.
Proof Since the result is already known forn=1, we supposen>1. Then eithern
orn−2 is congruent to 1 mod 4 and so, by Proposition 1 and Proposition 2(i),
( 2 /n)=(− 1 /n)((n− 2 )/n)=(− 1 /n)(n/(n− 2 ))=(− 1 )(n−^1 )/^2 ( 2 /(n− 2 )).Iterating, we obtain( 2 /n)=(− 1 )h,whereh=(n− 1 )/ 2 +(n− 3 )/ 2 +···+ 1 =
(n^2 − 1 )/8. The result follows.
The value of(a/n)whennis even is completely determined by Propositions 1
and 2. The evaluation of(a/n)whennis odd reduces by these propositions and Corol-
lary3totheevaluationof(m/n)for oddm>1. Although Proposition 2 does not
provide a formula for the Jacobi symbol in this case, it does provide a method for its
rapid evaluation, as we now show.
Ifmandnare relatively prime odd positive integers, we can writem= 2 hn+ε 1 n 1 ,
whereh∈Z,ε 1 =±1andn 1 is an odd positive integer less thann.Thennandn 1 are
also relatively prime and
(m/n)=(ε 1 /n)(n 1 /n).Ifn 1 =1, we are finished. Otherwise, using Proposition 2(i), we obtain
(m/n)=(− 1 )(n^1 −^1 )(n−^1 )/^4 (ε 1 /n)(n/n 1 )=±(n/n 1 ),