GATE2005-IT-34

2.5k views

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$.

1. $p(q - 1)$
2. $pq$
3. $\left ( p^{2}-1 \right ) (q - 1)$
4. $p(p - 1) (q - 1)$

edited
1
We can eliminate the options suppose $n=3^2*2=18, n=18, p=3$ and $q=2$
Numbers which are co-prime to $18:= 1,5,7,11,13,17$ there are 6 such numbers.

$(or)$ $18=3^2*2^1$, then numbers co-prime to $18:(3^2 - 3^1)*(2^1-2^0) = 6*1=6$

Now we can eliminate the options! $(C)$ is the correct one.

PS:This problem is same as to find the number of generators in a cyclic group of order n.
3

Euler totient function is used to find phi(n) is used to find all numbers which are relatively prime to n.

1. N= P^x * Q^y   where P and Q are prime numbers.

2. when x = 1 then phi(P ^x) is P-1

3. when x = n then phi(P^x) is P^n - P. (repeated roots)
0
for exam purpose we can easily use the option by elimination

take two prime numbers which is p=2 q=3 n=4*3=12

by putting the values in the option we get

1. 4

2. 6

3. 6

4.2*1*2=4

as per the given condition 1<=m<=n we can get (1,5,7,11) these numbers are our gcd

hence option 2 and 3 eliminited

now by considering one more prime number we can easily eliminate option 1 also

consider the as small as prime number so that calculation will not take more steps
0

@chauhansunil20th

D) correct option.

try with n=12.

Yes, it is Eular formula.

$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$

edited
0
Sir means the numbers we get after subtracting from "n" are the ones which do not contain p or q or pq in them,, and so their gcd with n will result to 1?
0
After subtraction we get numbers which are not multiple of p or q.
0
@arjun sir

can you please explain it a bit more, actually not getting it.
2
Since prime factorisation 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
1
Got it. Thanx
4
Maybe you want to tell that you have used Inclusion - Exclusion Theorom
1
yes, for gcd being 1 , m will not divisible by any multiple of p or q

for pq it is double subtraction. So, added it
0

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.

3
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 \}$.

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*}

0
best

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 ∅(pn) is pn-1(p-1)

given that n=p2q(p,q prime)

∅(p2q)=∅(p2)*∅(q)

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

0

0
Explain properly man ....
0
nice explanation!
1

Explaination for : ∅(p2).

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 ∅(p2).

1 vote
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
1 vote

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.

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

reshown by
0
how?

Related questions

1
4.1k views
Let $A$ be a set with $n$ elements. Let $C$ be a collection of distinct subsets of $A$ such that for any two subsets $S_1$ and $S_2$ in $C$, either $S_1 \subset S_2$ or $S_2\subset S_1$. What is the maximum cardinality of C? $n$ $n+1$ $2^{n-1} + 1$ $n!$
Let $f$ be a function from a set $A$ to a set $B$, $g$ a function from $B$ to $C$, and $h$ a function from $A$ to $C$, such that $h(a) = g(f(a))$ for all $a ∈ A.$ Which of the following statements is always true for all such functions $f$ and $g$? $g$ is onto $\implies$ $h$ is onto $h$ is onto $\implies$ $f$ is onto $h$ is onto $\implies$ $g$ is onto $h$ is onto $\implies$ $f$ and $g$ are onto
The minimum positive integer $p$ such that $3^{p} \pmod {17} = 1$ is $5$ $8$ $12$ $16$
The exponent of $11$ in the prime factorization of 300! is $27$ $28$ $29$ $30$