Question

Let n = $P^{2}q$, where p and q are distinct prime numbers. How many numbers m satisfy $1\le m\le$ 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)

Answer 1

The correct option is D p ( p - 1 )( q - 1)

The number of numbers from 1 to n, which are relatively prime to n i.e.., gcd (m,n)=1, is given by the Euler Totient function $\varphi$(n). If n is broken down into its prime factors as n = $P_1^{n_1}$ $P_2^{n_2}$....
where $P_1$ , $P_2$ etc. are distinct prime numbers,
then

$\varphi \left(n\right)=\varphi \left(P_1^{n_1}\right)\varphi \left(P_2^{n_2}\right)$

Here, $n=p^{2}q$
So, $\varphi \left(n\right)=\varphi \left(P^2\right)\times \varphi \left(q\right)$

Now, using the property $\varphi \left(P^k\right)=p^k-P^{k-1}$ ,
$\varphi \left(P^2\right)=P^2-P^1=P^2-P$ and
$\varphi \left(q\right)=q^1-q^0=q-1$

Substituting these in eq. (i), we get

$\varphi \left(n\right)=(p^2-p)(q-1)$
=$p(p-1)(q-1)$