Number Theory: An Introduction to Mathematics

130 III More on Divisibility

is a permutation ofX.WedefinetheJacobi symbol(a/n)to be sgn(πa),i.e.

(a/n)=1or− 1

according as the permutationπais even or odd. Thus(a/ 1 )=1, for every integer
a. (The definition is sometimes extended by putting(a/n)=0ifaandnare not
relatively prime.)

Proposition 1For any positive integer n and any integers a,b relatively prime to n,
the Jacobi symbol has the following properties:

(i)( 1 /n)= 1 ,
(ii)(a/n)=(b/n)if a≡bmodn,
(iii)(ab/n)=(a/n)(b/n),
(iv)(− 1 /n)= 1 if n≡ 1 or2mod4and=− 1 if n≡ 3 or0mod4.

Proof The first two properties follow at once from the definition of the Jacobi sym-
bol. Ifaandbare both relatively prime ton, then so also is their productab.Since
πab=πaπb,wehavesgn(πab)=sgn(πa)sgn(πb), which implies (iii). We now eval-
uate(− 1 /n). Since the mapπ− 1 :x→−xmodnfixes 0 and reverses the order of
1 ,...,n−1, the total number of inversions of order is(n− 2 )+(n− 3 )+···+ 1 =
(n− 1 )(n− 2 )/2. It follows that(− 1 /n)=(− 1 )(n−^1 )/^2 or(− 1 )(n−^2 )/^2 according as
nis odd or even. This proves (iv).

Proposition 2For any relatively prime positive integers m,n,

(i)if m and n are both odd, then(m/n)(n/m)=(− 1 )(m−^1 )(n−^1 )/^4 ;
(ii)if m is odd and n even, then(m/n)= 1 or(− 1 )(m−^1 )/^2 according as n≡ 2 or
0mod4.

Proof The cyclic permutationτ:x→x+1modnof the setX={ 0 , 1 ,...,n− 1 }
has sign(− 1 )n−^1 , since the number of inversions of order isn−1. Hence, for any
integerb≥0 and any integerarelatively prime ton, the linear permutation

τbπa:x→ax+bmodn

ofXhas sign(− 1 )b(n−^1 )(a/n).
PutY={ 0 , 1 ,...,m− 1 }andP=X×Y. We consider two transformationsμ
andvofP,definedby

μ(x,y)=(mx+ymodn,y), v(x,y)=(x,x+nymodm).

For each fixedy,μdefines a permutation of the set(X,y)with sign(− 1 )y(n−^1 )(m/n).
Since

∑m− 1

y= 0 y=m(m−^1 )/2, it follows that the permutationμofPhas sign

sgn(μ)=(− 1 )m(m−^1 )(n−^1 )/^2 (m/n)m.

Similarly the permutationvofPhas sign

sgn(v)=(− 1 )n(m−^1 )(n−^1 )/^2 (n/m)n,