Coprimes satisfying a pair We know that number of coprimes less than a number can be found using Euler's totient function.
But if there are two numbers $p$ and&nbsp;$q$ and we need to find number of numbers less than&nbsp;$q$ and coprime to&nbsp;$p$, is there any efficient method?
No.  This is as hard as factoring, and there is no known efficient algorithm for factoring.  In particular, there is a standard reduction to show that if you could compute Euler's totient function efficiently, then you could factor efficiently.