1

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?

Stahl
  • 23,212
Rn2dy
  • 231
  • 4
    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 02:12

1 Answers1

3

The answer is $\phi((q-1)(p-1))$, but to compute that you probably need to factor $p-1$ and $q-1$.

lhf
  • 216,483
  • 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 http://rjlipton.wordpress.com/2011/12/10/a-lemma-on-factoring/ for the main idea. – duckstar Mar 26 '13 at 01:45