Number Theory: An Introduction to Mathematics

III

More on Divisibility

In this chapter the theory of divisibility is developed further. The various sections of the
chapter are to a large extent independent. We consider in turn the law of quadratic reci-
procity, quadratic fields, multiplicative functions, and linear Diophantine equations.

1 TheLawofQuadraticReciprocity

Letpbe an odd prime. An integerawhich is not divisible bypis said to be aquadratic
residue,orquadratic nonresidue,ofpaccording as the congruence

x^2 ≡amodp

has, or has not, a solutionx. We will speak of thequadratic natureofamodp,
meaning whetherais a quadratic residue or nonresidue ofp.
Letqbe an odd prime different fromp.Thelaw of quadratic reciprocityconnects
the quadratic nature ofqmodpwith the quadratic nature ofpmodq. It states that if
eitherporqis congruent to 1 mod 4, then the quadratic nature ofqmodpis the same
as the quadratic nature ofpmodq, but if bothpandqare congruent to 3 mod 4 then
the quadratic nature ofqmodpis different from the quadratic nature ofpmodq.
This remarkable result plays a key role in the arithmetic theory of quadratic forms.
It was discovered empirically by Euler (1783). Legendre (1785) gave a partial proof
and later (1798) introduced the convenient ‘Legendre symbol’. The first complete
proofs were given by Gauss (1801) in hisDisquisitiones Arithmeticae. Indeed the re-
sult so fascinated Gauss that during the course of his lifetime he gave eight proofs, four
of them resting on completely different principles: an induction argument, the theory
of binary quadratic forms, properties of sums of roots of unity, and a combinatorial
lemma. The proof we are now going to give is also of a combinatorial nature. Its idea
originated with Zolotareff (1872), but our treatment is based on Rousseau (1994).
Letnbe a positive integer and letXbe the set{ 0 , 1 ,...,n− 1 }.Asin§7of
Chapter I, a permutationαofXis said to beevenoroddaccording as the total number
of inversions of order it induces is even or odd. Ifais an integer relatively prime ton,
then the mapπa:X→Xdefined by

πa(x)=axmodn

W.A. Coppel, Number Theory: An Introduction to Mathematics, Universitext, 129
DOI: 10.1007/978-0-387-89486-7_3, © Springer Science + Business Media, LLC 2009