2.9. EXERCISES 23
Theorem 2.8.4 (Fundamental theorem of arithmetic) Let a ∈ N\{1}. Then a =
∏ni=1 pi where pi are all prime numbers. Furthermore, this prime factorization is unique
except for the order of the factors.
Proof: If a equals a prime number, the prime factorization clearly exists. In particularthe prime factorization exists for the prime number 2. Assume this theorem is true for alla ≤ n− 1. If n is a prime, then it has a prime factorization. On the other hand, if n is nota prime, then there exist two integers k and m such that n = km where each of k and m areless than n. Therefore, each of these is no larger than n− 1 and consequently, each has aprime factorization. Thus so does n. It remains to argue the prime factorization is uniqueexcept for order of the factors.
Suppose ∏ni=1 pi = ∏
mj=1 q j where the pi and q j are all prime, there is no way to reorder
the qk such that m = n and pi = qi for all i, and n+m is the smallest positive integer suchthat this happens. Then by Theorem 2.8.3, p1|q j for some j. Since these are prime numbersthis requires p1 = q j. Reordering if necessary it can be assumed that q j = q1. Then dividingboth sides by p1 = q1,∏
n−1i=1 pi+1 = ∏
m−1j=1 q j+1. Since n+m was as small as possible for
the theorem to fail, it follows that n−1 = m−1 and the prime numbers, q2, · · · ,qm can bereordered in such a way that pk = qk for all k = 2, · · · ,n. Hence pi = qi for all i because itwas already argued that p1 = q1, and this results in a contradiction.
2.9 Exercises1. By Theorem 2.7.9 it follows that for a < b, there exists a rational number between a
and b. Show there exists an integer k such that a < k2m < b for some k,m integers.
2. Show there is no smallest number in (0,1) . Recall (0,1) means the real numberswhich are strictly larger than 0 and smaller than 1.
3. Show there is no smallest number in Q∩ (0,1) .
4. Show that if S ⊆ R and S is well ordered with respect to the usual order on R then Scannot be dense in R.
5. Prove by induction that ∑nk=1 k3 = 1
4 n4 + 12 n3 + 1
4 n2.
6. It is a fine thing to be able to prove a theorem by induction but it is even better tobe able to come up with a theorem to prove in the first place. Derive a formula for∑
nk=1 k4 in the following way. Look for a formula in the form An5 +Bn4 +Cn3 +
Dn2 +En+F. Then try to find the constants A,B,C,D,E, and F such that thingswork out right. In doing this, show
(n+1)4 =(
A(n+1)5 +B(n+1)4 +C (n+1)3 +D(n+1)2 +E (n+1)+F)
−An5 +Bn4 +Cn3 +Dn2 +En+F
and so some progress can be made by matching the coefficients. When you get youranswer, prove it is valid by induction.
7. Prove by induction that whenever n≥ 2,∑nk=1
1√k>√
n.
8. If r ΜΈ= 0, show by induction that ∑nk=1 ark = a rn+1
r−1 −a rr−1 .