How many numbers lie in the range of $1331$ and $3113$ (Endpoints Inclusive) such that they are not divisible by $2$ or $3$ or $5$?
I came across this Number System question and was not able to figure out the way to get the answer. At first I thought to separate out the numbers which are divisible by the LCM of $2$, $3$ & $5$ but this will still leave some numbers which will be exclusively divisible by any one of $2$ or $3$ or $5$.
Another method I found out to solve these type of questions is by using the Euler's Totient method but I am not aware of this.
So can someone please explain a general way to solve these types of question?
General question can be : How many numbers lie in the range of $A$ and $B$ such that they are not divisible by $x$ or $y$ or $z$ and so on?
Best Answer
Another approach:
An integer $n$ is not divisible by any of $2$, $3$, and $5$ if and only if $n$ is relatively prime to $30$; and this in turn occurs if and only if $n$ leaves one of the eight remainders: $1, 7, 11, 13, 17, 19, 23, $ or $29$ upon division by $30$.
Because remainders upon division by $30$ occur cyclically: among any $30$ consecutive integers, exactly $8$ will not be divisible by any of $2, 3, 5$.
The interval $1331$ to $3100$ contains $1770=59\cdot 30$ integers. So this interval will contain $59\cdot 8=472$ integers not divisible by any of $2, 3, 5$.
From $3101$ to $3113$, the remainders upon division by $30$ are $11, 12, ..., 23$. Of these, the five with remainders of $11, 13, 17, 19, 23$ will not be divisible by any of $2, 3, 5$.
So the total in the desired interval is $472 + 5=477$ integers not divisible by any of $2, 3, 5$.