The Euler's phi function for interval

Question

I've read about Euler's phi function. I know that we use it to calculate the number of co-prime numbers with n that are smaller than n. So, I want to know can we somehow use this function, to calculate the number of co-prime numbers with n in any interval? For example, if I want to know the number of three-digit numbers, that are co-prime with 60. I will be glad if you can help me with this!

Answer 1

Any $n$ consecutive numbers form a complete residue system modulo $n$. Hence within these numbers, there are exactly $\phi (n)$ numbers that are coprime to $n$.

In your case, the set of 3-digit numbers is actually $900$ consecutive numbers. Among every $60$ consecutive numbers, there are $\phi (60)$ numbers that are coprime to $60$.

Since $900$ is a multiple of $60$, there are exactly $\left(\dfrac {900}{60} \phi(60)\right)$ 3-digit numbers coprime to $60$.

Answer 2

For multiples of $60$, it is easy: the number of natural numbers less than $60m$ that is coprime to $60$ is just $m\cdot\phi(60)$. That's because the pattern of coprimes and non-coprimes of 60 repeats with a period of 60.

In fact, it repeats with a period of 30 (30 is the result of multiplying all the unique primes in the factorisation of 60), so multiples of 30 are easy: the number of natural numbers less than $30n$ that is coprime to $60$ is just $n\cdot\frac{\phi(60)}{2}$. In fact, the same is true for any interval of $30n$ consecutive integers.

As the set of 3-digit numbers is an interval with $30\cdot30$ integers, we get that there are $30\cdot 8=240$ three-digit numbers that are coprime to 60.

When the period length doesn't go nicely into the length of the interval as discussed above, things get a bit more complicated. Your best bet is probably to find the closest whole multiple of the period length, then check each of the remaining numbers by hand. For instance, three-digit numbers whose first digit is 1 gives an interval of length 100. Use the above approach on the first 90 (up to and including 189), then check 190 up to 199 one by one.