8 Number Theory
Number theoryis the study of the integers.Whyanyone would want to study the
integers is not immediately obvious. First of all, what’s to know? There’s 0, there’s
1, 2, 3, and so on, and, oh yeah, -1, -2,.... Which one don’t you understand?
Second, what practical value is there in it?
The mathematician G. H. Hardy expressed pleasure in its impracticality when he
wrote:
[Number theorists] may be justified in rejoicing that there is one sci-
ence, at any rate, and that their own, whose very remoteness from or-
dinary human activities should keep it gentle and clean.
Hardy was specially concerned that number theory not be used in warfare; he was
a pacifist. You may applaud his sentiments, but he got it wrong: Number Theory
underlies modern cryptography, which is what makes secure online communication
possible. Secure communication is of course crucial in war—which may leave poor
Hardy spinning in his grave. It’s also central to online commerce. Every time you
buy a book from Amazon, use a certificate to access a web page, or use a PayPal
account, you are relying on number theoretic algorithms.
Number theory also provides an excellent environment for us to practice and
apply the proof techniques that we developed in previous Chapters. We’ll work out
properties of greatest common divisors (gcd’s) and use them to prove that integers
factor uniquely into primes. Then we’ll introduce modular arithmetic and work out
enough of its properties to explain the RSA public key crypto-system.
Since we’ll be focusing on properties of the integers, we’ll adopt the default
convention in this chapter thatvariables range over the set,Z, of integers.
8.1 Divisibility
The nature of number theory emerges as soon as we consider thedividesrelation,
where
Definition 8.1.1.
ajbWWD ŒakDbfor somekç:
The divides relation comes up so frequently that multiple synonyms for it are
used all the time. The following phrases all say the same thing:
