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?
how to find co-prime numbers
1
$\begingroup$
cryptography
-
4The 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$. – 2010-10-11