132 III More on Divisibility
where the minus sign holds if and only ifnandε 1 n 1 are both congruent to 3 mod 4.
The process can now be repeated withm,nreplaced byn,n 1. After finitely many steps
the process must terminate withns=1.
As an example,
(
2985
1951
)
=
(
− 1
1951
)(
917
1951
)
=−
(
1951
917
)
=−
(
117
917
)
=−
(
917
117
)
=−
(
− 1
117
)(
19
117
)
=−
(
117
19
)
=−
(
3
19
)
=
(
19
3
)
=
(
1
3
)
= 1.
Further properties of the Jacobi symbol can be derived from those already estab-
lished.
Proposition 4If n,n′are positive integers and if a is an integer relatively prime to n
such that n′≡nmod 4a, then(a/n′)=(a/n).
Proof Ifa=−1 then, sincen′≡nmod 4,(a/n′)=(a/n), by Proposition 1(iv). If
a=2 then, sincenandn′are odd andn′≡nmod 8,(a/n′)=(a/n), by Corollary 3.
Consequently, by Proposition 1(iii), it is sufficient to prove the result for odda>1.
Ifnis even, the result now follows from Proposition 2(ii). Ifnis odd, it follows
from Proposition 2(i) and Proposition 1.
Proposition 5If the integer a is relatively prime to the odd positive integers n and n′,
then(a/nn′)=(a/n)(a/n′).
Proof We h av ea≡a′modnn′for somea′∈{ 1 , 2 ,...,nn′}.Sincenn′is odd, we
can choosej∈{ 0 , 1 , 2 , 3 }so thata′′=a′+jnn′satisfiesa′′≡1 mod 4. Then, by
Propositions 1 and 2,
(a/nn′)=(a′′/nn′)=(nn′/a′′)=(n/a′′)(n′/a′′)=(a′′/n)(a′′/n′)=(a/n)(a/n′).
Proposition 5 reduces the evaluation of(a/n)for odd positivento the evaluation of
(a/p),wherepis an odd prime. This is where we make the connection with quadratic
residues:
Proposition 6If p is an odd prime and a an integer not divisible by p, then(a/p)= 1
or− 1 according as a is a quadratic residue or nonresidue of p. Moreover, exactly half
of the integers 1 ,...,p− 1 are quadratic residues of p.
Proof Ifais a quadratic residue ofp, there exists an integerxsuch thatx^2 ≡amodp
and hence
(a/p)=(x^2 /p)=(x/p)(x/p)= 1.