SECTION 2.1 Elementary Number Theory 79
(c) Conclude from part (b) that there must be infinitely many
primes.- Here’s yet another proof that there are infinitely many primes^13
We start with the simple observation that for any integern≥2,n
andn+ 1 share no prime factors. Therefore, the productn(n+ 1)
must contain at least two distinct prime factors. We now generate
a sequence of integers as follows. Let
n 1 = 2· 3
n 2 = n 1 (n 1 + 1) = 42
n 3 = n 2 (n 2 + 1) = 42·43 = 1806What is the minimum number of distinct prime factors contained
innk?- For any positive integern, letτ(n) be the number of divisors (in-
cluding 1 andn) ofn. Thusτ(1) = 1, τ(2) = 2, τ(3) = 2, τ(4) =
3 , τ(10) = 4, etc. Give a necessary and sufficient condition for
τ(n) to be odd. - Continuation of Exercise 10. For each positive integern, set
S(n) =τ(1) +τ(2) +···+τ(n).Letabe the number of integersn≤2000 for whichS(n) is even.
Computea.^142.1.5 The Principle of Mathematical Induction
In the previous section we showed that every integernhas at least one
prime factor essentially by dividing the setNinto the two subsets: the
set of all integersnwhich have a prime factor, and set of those which
do not. This latter set was dubbed the set of “criminals” for the sake
(^13) See Filip Saidak,A New Proof of Euclid’s Theorem, Amer. Math. Monthly, Vol. 113,
No. 9, Nov., 2006, 937–938. 14
This is a modification of Problem #12 of the American Invitational Mathematics Examination,
2005 (I).