Exercises outline two additional proofs that there are infinitely many primes.Suppose that...

Exercises outline two additional proofs that there are infinitely many primes.

Suppose that p1,…, pj are the first j primes, in increasing order. Denote by Ν (x) the number of integers n not exceeding the integer x that are not divisible by any prime exceeding pj.

a) Show that every integer n not divisible by any prime exceeding pj can be written in the form n = r2s, where s is square-free.

---

b) Show there are only 2j possible values of s in part (a) by looking at the prime factorization of such an integer ft, which is a product of terms , where 0 ≤ k ≤ j and ek is 0 or 1.

---

c) Show that if n ≤ x, then , where r· is in part (a). Conclude that there are no more than  different values possible for r. Conclude that .

---

d) Show that if the number of primes is finite and pj is the largest prime, then N(x) = x for all integers x.

---

e) Show from parts (c) and (d) that , so that x ≤ 22j for all x, leading to a contradiction. Conclude that there must be infinitely many primes.