# how to find co-prime numbers

Suppose $p$ and $q$ are two prime numbers. How can one quickly calculate how many numbers $x$ there are such that $\gcd(x, (q-1)\cdot(p-1)) = 1$, without using brute force?

-
The number is infinite; presumably you mean how many positive numbers strictly smaller than some bound; for those smaller than $(p-1)(q-1)$ you can use Euler's totient function, provided you can factor $p-1$ and $q-1$. –  Arturo Magidin Oct 11 '10 at 2:12

The answer is $\phi((q-1)(p-1))$, but to compute that you probably need to factor $p-1$ and $q-1$.
For any positive integer $n$ given $\phi(n)$ the factorization of $n$ can be found in probabilistic polynomial time or deterministically under the Extended Riemann Hypothesis. See for example rjlipton.wordpress.com/2011/12/10/a-lemma-on-factoring for the main idea. –  David Marquis Mar 26 '13 at 1:45