1. Show that any integer n can be written uniquely as n = nim, where m...

 

Transcribed Image Text:

1. Show that any integer n can be written uniquely as n = nim, where m is squarefree, i.e. is not divisible by any square of a prime. [10 marks] 2. Let Pj be the jth prime for some je N. Let N; (x) be the number of n ≤ x which are not divisible by any prime p > pj. Using the question above, show that N, (x) ≤ 2³√x. [30 marks] 3. Infer that N, (x) < x for large enough x, and therefore that there are infinitely many primes. [10 marks] 4. Show that the number of positive integers n ≤ x divisible by some integer d is at most x/d and hence that x - N;(x) = Σ k>j X 1 Σ < 1/2. Pk k>j Conclude using questions 2 and 4. [20 marks] Pk (where it is understood that any number is less than infinity). [10 marks] 5. Show that the series of reciprocals of primes is divergent. Hint: if it is conver- gent, let j be such that log Hint: 2 log 2* 6. Prove that the number 7(x) of primes p ≤ x satisfies (x) > consider N() (x) and question 2. How does it compare to the bound obtained using Euclid's proof of infinitude of primes? [20 marks] 1. Show that any integer n can be written uniquely as n = nim, where m is squarefree, i.e. is not divisible by any square of a prime. [10 marks] 2. Let Pj be the jth prime for some je N. Let N; (x) be the number of n ≤ x which are not divisible by any prime p > pj. Using the question above, show that N, (x) ≤ 2³√x. [30 marks] 3. Infer that N, (x) < x for large enough x, and therefore that there are infinitely many primes. [10 marks] 4. Show that the number of positive integers n ≤ x divisible by some integer d is at most x/d and hence that x - N;(x) = Σ k>j X 1 Σ < 1/2. Pk k>j Conclude using questions 2 and 4. [20 marks] Pk (where it is understood that any number is less than infinity). [10 marks] 5. Show that the series of reciprocals of primes is divergent. Hint: if it is conver- gent, let j be such that log Hint: 2 log 2* 6. Prove that the number 7(x) of primes p ≤ x satisfies (x) > consider N() (x) and question 2. How does it compare to the bound obtained using Euclid's proof of infinitude of primes? [20 marks]