# The number of numbers not divisible by $2,3,5,7$ or $11$ between multiples of $2310$

Looking at partitions of the natural number line of the form $P=[a,b)$, I noted that

• if $a$ and $b$ are multiples of $6$, there exist at least $2$ numbers in the partition which are not divisible by $2$ or $3$
• if $a$ and $b$ are multiples of $30$, there exist $8$ numbers in the partition which are not divisible by $2, 3$ or $5$
• if $a$ and $b$ are multiples of $210$, there exist $54$ numbers in the partition which are not divisible by $2,3,5$ or $7$.

This leads me to guess that if $a$ and $b$ are multiples of $2310$, there exist $592$ numbers in the partition which are not divisible by $2,3,5,7$ or $11$. Is this true?

(I arrived at $592$ because it is equal to $54 \times 11 - 2$ and $2310$ because it is equal to $210 \times 11$.)

• – vadim123 Mar 16 '14 at 14:43
• Good work! I believe you will find that for $210$ it is $48$, not $54$. You are in the process of discovering the Euler $\varphi$ function. – André Nicolas Mar 16 '14 at 14:48
• @Andre Thank you! I noted that are 35 primes between 210 and 420 as well as 8 numbers whose lowest divisor is 11, 6 with ld=13, 3 with ld=17 and 2 with ld=19, hence the 54...? – Brad Graham Mar 16 '14 at 14:56
• You have done some "double-counting." – André Nicolas Mar 16 '14 at 15:32
• I'll double check cheers – Brad Graham Mar 16 '14 at 15:33

Use chinese remainder representation with basis $[2,3,5,7,11]$.
Given a CRR basis $[a,b,c,d,e]$ with $M = abcde = 2\times 3 \times 5 \times 7 \times 11 = 2310$, each valid tuple represents exactly 1 number from $0$ to $M - 1 \pmod M$. So you want the number of tuples that don't contain a zero, or $(a - 1)(b - 1)(c - 1)(d - 1)(e - 1)$ or $1 \times 2 \times 4 \times 6 \times 10 = 480$.