88 6. Integers, Divisors, and Primes
6.1.1Check (using the definition) that 1|a,− 1 |a,a|aand−a|afor every
integera.
6.1.2What does it mean fora, in more everyday terms, if (a) 2|a; (b) 2a;
(c) 0|a.
6.1.3Prove that
(a) ifa|bandb|cthena|c;
(b) ifa|banda|cthena|b+canda|b−c;
(c) ifa, b >0 anda|bthena≤b;
(d) ifa|bandb|athen eithera=bora=−b.6.1.4Letrbe the remainder of the divisionb÷a. Assume thatc|aandc|b.
Prove thatc|r.
6.1.5Assume thata|b, anda, b >0. Letrbe the remainder of the division
c÷a, and letsbe the remainder of the divisionc÷b. What is the remainder of
the divisions÷a?
6.1.6 (a) Prove that for every integera,a− 1 |a^2 −1.
(b) More generally, for every integeraand positive integern,a− 1 |an− 1.6.2 Primes and Their History
An integerp>1 is called aprimeif it is not divisible by any integer other
than 1,− 1 ,p, and−p. Another way of saying this is that an integerp> 1
is a prime if it cannot be written as the product of two smaller positive
integers. An integern>1 that is not a prime is calledcomposite(the
number 1 is considered neither prime nor composite). Thus 2, 3 , 5 , 7 ,11 are
primes, but 4 = 2·2,6=2·3,8=2·4, 9 = 3·3, 10 = 2·5 are not primes.
Table 6.1 shows the primes up to 500.
Primes have fascinated people ever since ancient times. Their sequence
seems very irregular, yet on closer inspection it seems to carry a lot of
hidden structure. The ancient Greeks already knew that there are infinitely
many such numbers. (Not only did they know this; they proved it!)
It was not easy to prove any further facts about primes. Their sequence
is reasonably smooth, but it has holes and dense spots (see Figure 6.1).
How large are these holes? For example, is there a prime number with any
given number of digits? The answer to this question will be important for
us when we discuss cryptography. The answer is in the affirmative, but this
fact was not proved until the mid-nineteenth century, and many similar
questions are open even today.