6.4 On the Set of Primes 936.3.6Prove that ifpis a prime, then
√
pis irrational. More generally, prove
that ifnis an integer that is not a square, then
√
nis irrational.6.3.7Try to formulate and prove an even more general theorem about the
irrationality of the numbersk
√
n.6.4 OntheSetofPrimes......................
The following theorem was known to Euclid in the third centuryB.C.
Theorem 6.4.1There are infinitely many primes.
Proof. What we need to do is to show that for every positive integern,
there is a prime number larger thann. To this end, consider the number
n! + 1, and any prime divisorpof it. We show thatp>n. Again, we use an
indirect proof, supposing thatp≤nand deriving a contradiction. Ifp≤n
thenp|n!, since it is one of the integers whose product isn!. We also know
thatp|n! + 1, and sopis a divisor of the difference (n!+1)−n! = 1. But
this is impossible, and thuspmust be larger thann.
If we look at various charts or tables of primes, our main impression is
that there is a lot of irregularity in them. For example, Figure 6.1 represents
each prime up to 1000 by a bar. We see large “gaps”, and then we also see
primes that are very close. We can prove that these gaps get larger and
larger as we consider larger and larger numbers; somewhere out there is
a string of 100 consecutive composite numbers; somewhere (much farther
away) there is a string of 1000 consecutive composite numbers, etc. To state
this in a mathematical form:
Theorem 6.4.2For every positive integerk, there existk consecutive
composite integers.
Proof. We can prove this theorem by an argument quite similar to the
proof of Theorem 6.4.1. Letn=k+ 1 and consider the numbers
n!+2,n!+3, ..., n!+n.Can any of these be a prime? The answer is no: The first number is even,
sincen! and 2 are both even. The second number is divisible by 3, since
n! and 3 are both divisible by 3 (assuming thatn>2). In generaln!+i
is divisible byi, for everyi=2, 3 ,...,n. Hence these numbers cannot be
primes, and so we have foundn−1=kconsecutive composite numbers.
What about the opposite question, finding primes very close to each
other? Since all primes except 2 are odd, the difference between two primes