GATE IT 2005 | Question: 34

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. $\left ( p^{2}-1 \right ) (q - 1)$
• D. $p(p - 1) (q - 1)$

Comments

@chauhansunil20th

D) correct option.

try with n=12.

Yes, it is Eular formula.

---

This question can be easily solved by principle of inclusion exclusion. No of numbers from 1 to n that are divisible by p are n/p (only integer value). Similarly no of numbers that are divisible by q are n/q. Now we have counted those nos twice that are divisible by pq(which is n/pq). So we need to subtract it once. So total numbers from 1 to n that are co-prime(gcd=1) of n = n-(n/p + n/q – n/pq). Substitute n=p^2q you will get the answer.

---

@chauhansunil20th thanks for the shortcut and also small correction answer is d not c needs an edit

Answer 1

$n = p^2q,$ where $p$ and $q$ are prime.

So, number of multiples of $p$ in $n = pq$

Number of multiples of $q$ in $n = p^2$

Number of multiples of $pq$ in $n = p$

Since, prime factorization of $n$ consists of only $p$ and $q, gcd(m, n)$ will be a multiple of these or $1.$ So, number of possible $m$ such that $gcd(m, n)$ is $1$ will be $n -$ number of multiples of either $p$ or $q$

$\quad \quad = n - p^2-pq+p$
$\quad \quad= p^2q-p^2-pq+p$
$\quad \quad= p(pq-p-q+1)$
$\quad \quad=p(p-1)(q-1)$

Correct Answer: $D$

Comments

So, number of multiples of p in n is pq

I'm skeptical about the correctness of this sentence and hence of the solution.  Number of multiples of p should be 2*2. Let's take an example.  

$n = 2^{2}*3$

Here, number of multiples of 2 in n is 4 which are $1,2,3,6$. 

 

Please correct me where I'm wrong.  

 

 

---

No. of multiples of $x$ in $\left \{ 1, \ 2, \ 3, \ \dots , \ n \right \}$ is given by $\lfloor \frac{n}{x} \rfloor$.

$\therefore$ No. of multiples of $2$ in $\left \{ 1, \ 2, \ 3, \ \dots , \ 12 \right \}$ is $\lfloor \frac{12}{2} \rfloor = 6$, i.e $\left \{ 2, \ 4, \ 6, \ 8, \ 10, \ 12 \right \}$.

---

"number of multiples of p in n (i.e. p²q) means" -: "number of multiples of p from p to p²q" ​

e.g. no. of multiples of 2 in 2²3 = 2×3 i.e. 6 ​, no. of multiples of 3 in 2²3 = 2×2 i.e. 4 

Answer 2

Euler's totient function $\phi (n)$ is being asked here :

Euler's totient function $\phi (n)$ = Number of positive integers which are $\leq n$ and relatively prime or co-prime to $n.$ (ie. co-prime means if  $\gcd (a,b)=1$ )

It is given by $\phi (n)= n\times( \frac{(P_1-1)(P_2-1)\ldots (P_k-1)}{P_1 P_2..P_k} )$

$\text{where } P_1 P_2\ldots P_k \ \ \text{distinct prime divisors of }n$

We have $n=p^{2}q$.

Therefore,
$\begin{align*} \phi(n)&= n(\frac{(p-1)(q-1)}{p q}) \\ &= p^{2}q(\frac{(p-1)(q-1)}{p q}) \\ &= p (p-1)(q-1) \end{align*}$

Comments

best

---

This is the best answer...

Answer 3

using Eulers function we can find out the no of relatively prime factors.

If we find out gcd of n with any of these prime factor,it will be always 1.

Eulers function is ∅(pⁿ) is p^n-1(p-1) 

given that n=p²q(p,q prime)

∅(p²q)=∅(p²)*∅(q)

          =p(p-1)(q-1)

so D is the answer

Comments

Please provide derivation of ∅(p²). 

---

Explain properly man ....

---

nice explanation!

---

Explaination for : ∅(p²). 

Let take n = 50 , then its prime factorization will be 5*5*2 => 5^2 * 2.

∅(50)= ∅(5^2) * ∅(2)

Aa we know that when any of prime factor let say x, has more then one power let say m then ∅(x^m) = x(x-1). 

Hence, ∅(50)= ∅(5^2) * ∅(2) 

= 5*(5-4) * (2-1)

= 5 * 4 * 1

= 20

Same logic can be applied for ∅(p²).

    

Answer 4

Trial and Error technique:

 

Trial 1:

 

Let p=2, q=3

Therefore, n=12

 

Conditions to be satisfied:

 

1<=m<=12 

gcd(m,12)=1

 

Therefore, m could be => 1,5,7,9 => 4 values

Choices A & D satisfy

 

Trial 2: 

 

Let p=3, q=2

Therefore, n=18

 

Conditions to be satisfied:

 

1<=m<=18

gcd(m,18)=1

 

Therefore, m could be => 1,5,7,11,13,17 => 6 values

Choice A not satisfied, Choice D satisfied. Therefore, D.

 

Comments

I like this technique even I tried this.

---

In trial-1, m cannot be 9 because gcd(9,12)=3
m = {1, 5, 7, 11}

Answer 5

This question is dealing with all the 3 cases of Euler's totient function

$\phi (n)$ = n - 1 when n is a prime number.

$\phi (n)$ = $\phi (p)$$\phi (q)$  if n = p.q  & both p and q are prime numbers

$\phi (n)$ = $p^{k} - p^{k-1}$  if n = $p^{k}$ where p is prime.

now, $\phi (n)$ = $\phi (p^{2}.q)$ =$\phi (p^{2}).\phi (q)$ = $(p^{2} - p^{1}).(q-1)$ = p.(p-1).(q-1)

option D is correct

Answer 6

For p=2 and 1 =3 both option a and option d were satisfied , but for p= 3 and q =5 option d satisfies .