189-235A: Basic Algebra I

Assignment 2

Due: Wednesday, September 17.

1. Page 31, 1.30 and 1.31.

2. Page 34, 1.41, 1.44, 1.45 and 1.46.

3. (The infinitude of primes).

a) Show that if n>2 there is always a prime p such that n!+1>p>n.. 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 the product, taken over all primes p less than or equal to N, of the expression 1/(1-1/p), is equal to the (infinite) sum of 1/n taken over all the N-smooth integers n>0. (Hint: use the formula for the sum an infinite geometric series to rewrite 1/(1-1/p) as an infinite sum. Note the crucial role played by the fundamental theorem of arithmetic in your argument.)

c) Show that the product evaluated in part b) tends to inifinity as N tends to infinity. 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. It is more complicated that Euclid's proof, but it also carries more information, as we show in part d).

d) Show that the sum of 1/p taken over all the primes p diverges. (Hint: apply the natural logarithm log to the result of part c, and use the infinite series expression for log(1/(1-x)).