Let $m$ and $n$ be two integers such that $m>n$. Then find the number of integers less than $m$ and relatively prime to $n$.
I had come across a problem of this type with specific values for $m$ and $n$, unfortunately, the values I don't remember anymore. So I asked this general question. How to solve this type of question?
My thoughts are that we need to count the numbers. So we can count the number of integers less than $m$ and relatively prime to $m$ using Euler's totient function. Now among those numbers, also belongs the numbers which are relatively prime to $n$. We can also find the numbers less than $n$ and relatively prime to $n$. That will give a rough estimation. But how do we know about the actual number of such integers? Can anybody help me with this?
Thanks.
Best Answer
If primes $p_1, p_2$ are the only prime factors of $n$, then we get numbers relatively prime to $n$ and less than $m$ are (assuming $p_1, p_2$ are not factors of $m$):
$$m - \lfloor\frac{m}{p_1}\rfloor - \lfloor\frac{m}{p_2}\rfloor + \lfloor\frac{m}{p_1p_2}\rfloor$$
We can have a generalized expression for any number of prime factors of $n$ using PIE.