5. [6 marksl primes Since, as shown in the course notes, there are infinitely ma

Question

5. [6 marksl primes Since, as shown in the course notes, there are infinitely many primes, it is not possible for a consecutive sequence of composite (non-prime) natural numbers to stretch on forever. However, arbitrarily long prime-free sequences exist. On the other hand, for any natural number we can always set an upper bound on how far away the next prime can be. Prove each of the following statements. You may use the Prime predicate (a) 13 marks] Claim: For any k E N there is some n E N such that n,n+1,. ,n + k are composite. Hint Think about k 1)!. (b) (3 marks] Claim: For any positive natural number n there exists a prime p with n

Explanation / Answer

(a) for any k we have to find a sequence of k+1 consecutive integers the first term of which is n.

let k be given.

Let n=(k+2)! And consider the consecutive integers :

(k+2)! + 2 , (k+2)!+3, (k+2)!+4, ..., (k+2)!+(k+2)

Here are k+1 consecutive integers as desired.

Now we have to show these are all composites.

Note that (k+2)! is the product of first k+2 positive integers. Hence all the numbers less than or equal to k+2 occur in the factorial.

The i'th term is of the form (k+2)! + (i+1) where i varies from 1 to k+1 & as noted above, i+1 is less than or equal to k+2 and occurs in the factorial hence we can take common i+1 from them as a factor & the other factor is greater than 1.

Hence we get 2 factors of the number both of which are greater than 1. Hence (k+2)!+(i+1) is composite for all i between 1 to k+1.

Hence we het a sequence of k+1 consecutive integers all of which are composites.

(b) for n=1, we have 1<2< 1!+2, as the base case holds.

For n=2 we have p=3

For n>=3, consider n!+2 which is always composite.

Let p be the largest prime number which is less than n!+2 & divides n!+2.

If p<=n then p occurs is n! . Hence p divides n!

Hence p divides n!+2 - n!

i.e. p divides 2, hence p = 2 , which is not the case for all n, since p is largest by choice.

Hence we must have n<p.

Hence there exists prime p such that n<p<n!+2

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.