189-235A: Basic Algebra I Assignment 2

Due: Wednesday, September 18.

Section 1.1: 1,8. Section 1.2: 1, 30, 36. Section 1.3: 11, 12, 21, 26.

10. (The infinitude of primes).

a) Show that if n > 2 there is always a prime p such that n < p < n! + 1. Be sure to explain why this proof breaks down for n = 2. Conclude that there are infinitely many primes. This proof dates back to Euclid.

b) An integer is said to be N-smooth if all its prime divisors are less than or equal to N. Show that

∏_{p≤N} \frac{1}{1 − \frac{1}{p}} = ∑_{n N−smooth} \frac{1}{n},

where the product on the left is taken over the primes less than N, and the (infinite) sum on the right is taken over all the N-smooth integers n ≥ 1. (Hint: remember how to sum an infinite geometric series! Note also the crucial role played by the fundamental theorem of arithmetic in your argument.)

c) Show that

lim_{N⟶∞} ( ∏_{p≤N} \frac{1}{1 − \frac{1}{p}} ) = ∞,

and conclude that there are infinitely many primes. This remarkable proof was discovered by Leonhard Euler and is one of the great mathematical achievements of the 18th Century. But you might wonder why one bothers with a proof that is so much more involved than Euclid’s. This brings us to part d!

d) Show that

∑_{p} \frac{1}{p} = ∞,

where the sum is taken over the primes. (Hint: apply the natural logarithm log to the result of part c, and recall that log \frac{1}{1−x} = x + \frac{x^{2}}{2} + \frac{x^{3}}{3} + · · ·.)