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^2-1)(q-1)$
• B. p ( p - 1 )( q - 1)
• C. pq
• D. p (q - 1 )

Answer 1

The correct option is B 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.aredistinctprimenumbers,$
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-Pand$
$\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)$