文档介绍：Chapter 1
The Fundamental Theorem of
Arithmetic
Prime numbers
If a, b ∈ Z we say that a divides b (or is a divisor of b) and we write a | b, if
b = ac
for some c ∈ Z.
Thus −2 | 0 but 0 - 2.
Definition The number p ∈ N is said to be prime if p has just 2 divisors in N,
namely 1 and itself.
Note that our definition excludes 0 (which has an infinity of divisors in N) and
1 (which has just one).
Writing out the prime numbers in increasing order, we obtain the sequence of
primes
2, 3, 5, 7, 11, 13, 17, 19, . . .
which has fascinated mathematicians since the ancient Greeks, and which is the
main object of our study.
Definition We denote the nth prime by pn.
Thus p5 = 11, p100 = 541.
It is convenient to introduce a kind of inverse function to pn.
Definition If x ∈ R we denote by π(x) the number of primes ≤ x:
π(x) = k{p ≤ x : p prime}k.
Thus
π() = 0, π() = 2.
Evidently π(x) is monotone increasing, but discontinuous with jumps at each
prime x = p.
1–1
374 1–2
Theorem (Euclid’s First Theorem) The number of primes is infinite.
Proof I Suppose there were only a finite number of primes, say
p1, p2, . . . , pn.
Let
N = p1p2 · · · pn + 1.
Evidently none of the primes p1, . . . , pn divides N.
Lemma Every natural number n > 1 has at least one prime divisor.
Proof of Lemma B The smallest divisor d > 1 of n must be prime. For otherwise
d would have a divisor e with 1 < e < d; and e would be a divisor of n smaller
than d. C
By the lemma, N has a prime factor p, which differs from p1, . . . , pn. J
Our argument not only shows that there are an infinity of primes; it shows that
2n
pn < 2 ;
a very feeble bound, but our own. To see this, we argue by induction. Our proof
shows that
pn+1 ≤ p1p2 · · · pn + 1.
But now, by our inductive hypothesis,
21 22 2n
p1 < 2 , p2 < 2 , . . . , pn < 2 .
It follows that
21+22+···+2n
pn+1 ≤ 2
But
21 + 22 + · · · + 2n = 2n+1 − 1 < 2n+1.
Hence
2n+1
pn+1 < 2