Let n = p^2 * q where p and q are distinct prime numbers. How many numbers m satisfy 1

Question

Let n = p^2 * q where p and q are distinct prime numbers. How many numbers m satisfy 1 <= m <= n and gcd(m, n) = 1? Note that gcd(m, n) is the greatest common divisor of m and n.
A. p(q-1)
B. pq
C. (p^2-1)(q-1)
D. p(p-1)(q-1)

Accepted Answer

The number of m with 1 <= m <= n and gcd(m, n) = 1 is p(p-1)(q-1), which is option D. The count of integers from 1 to n that are coprime to n is Euler's totient function phi(n). For n = p^2 * q (p and q distinct primes), phi(n) = phi(p^2) * phi(q) = p^2(1 - 1/p) * q(1 - 1/q) = p(p-1)(q-1). This counts m values with no shared prime factor with p^2 * q.

Let n = p^2 * q where p and q are distinct prime numbers. How many numbers m satisfy 1 <= m <= n and gcd(m, n) = 1? Note that gcd(m, n) is the greatest common divisor of m and n. A. p(q-1) B. pq C. (p^2-1)(q-1) D. p(p-1)(q-1)