Prove that for every natural $n\geq6$, the set $\{n+1,\cdots, n+30\}$ contains no more than eight prime numbers using inclusion-exclusion principle.

80 Views Asked by At

Honestly, I have no idea how to prove that but I noticed that if we try to find the number of coprimes with $30$ that are less than $30$, we will get $22$ numbers that are not coprime using the exclusion inclusion principle and then $30 - 22 = 8$ coprimes.

Is this related somehow?

2

There are 2 best solutions below

3
On BEST ANSWER

Consider the set $S=\{2,3,5\}$ of primes. By inclusion–exclusion, the count of integers in $[n+1,n+30]$ that are coprime to all primes in $S$ is

\begin{eqnarray} \sum_{P\subset S}(-1)^{|P|}\frac{30}{\prod_{p\in P}p} &=& \frac{30}1-\frac{30}2-\frac{30}3-\frac{30}5+\frac{30}{2\cdot3}+\frac{30}{5\cdot2}+\frac{30}{3\cdot5}-\frac{30}{2\cdot3\cdot5} \\ &=& 30-15-10-6+5+3+2-1 \\ &=&8\;. \end{eqnarray}

0
On

A method without using Inclusion-Exclusion would be as follows:
Notice that if you take the elements of the set modulo $30$, you will get values $0$ to $29$. Of these, $\phi(30) = 8$ elements are not divisible by $2,3,5$. (That is: $1,7,11,13,17,19,23,29 \pmod {30}$). Whatever the value of $n$, the other $22$ elements are divisible by 2,3 and/or 5, so they are composite since $n \ge 6$. Thus, these $8$ elemnts are potential candidates of primes (of course, they may be divisible by a prime $p > 5$). Thus, the given set contains no more than $8$ primes.