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 $q$ and we need to find number of numbers less than $q$ and coprime to $p$, is there any efficient method?

  • $\begingroup$ You seem to be suggesting that computing the Euler totient function provides an easy way to find out the number of coprimes less than a number. But that's the definition of the function -- is there any known efficient way of actually computing it? $\endgroup$ – David Richerby Apr 2 '19 at 17:19
  • $\begingroup$ It involves computing the prime factorization of the number, which isn't known to be easy. Also, I've just noticed that the article you linked is just a rip-off of Wikipedia, so I've changed that to point to the original. Please don't encourage Wikipedia rip-offs. $\endgroup$ – David Richerby Apr 2 '19 at 18:44

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.