189-235A: Basic Algebra I Assignment 2

Due: Wednesday, September 28.

1. Prove or disprove: Let a, b, c be integers. If a divides b + c, then a divides both b and c.

2. Show than if a divides bc, it need not be the case that a divides either b or c.

3. Let R be the ring of elements of the form a + b\sqrt{−11}, where a and b are in Z. An element p of R is said to be a prime in R if any divisor of p in R is either 1, −1, p, or −p. Show that p = 3 is a prime in R. Find elements a and b in R such that p = 3 divides ab but p divides neither a nor b.

4. Show that if n > 2 is an integer, there is always a prime p in N such that n < p ≤ n! + 1. Conclude that there are infinitely many primes.

5. 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.)

6. 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. You might wonder why one bothers with a proof that is so much more involved than Euclid’s. This brings us to the next problem!

7. (Bonus question.) Show that

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

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