GATE CSE
First time here? Checkout the FAQ!
x
+8 votes
452 views

Let n = p2q, 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. (p2- 1) (q - 1)
  4. p(p - 1) (q - 1)
asked in Set Theory & Algebra by Veteran (19.1k points)   | 452 views

4 Answers

+10 votes
Best answer

n = p2q, where p and q are prime. 

So, number of multiple of p in n = pq 

Number of multiples of q in n = p2

Number of multiples of pq in n = p

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.

= n - p2-pq+p

= p2q-p2-pq+p

= p(pq-p-q+1)

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

answered by Veteran (283k points)  
selected by
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?
After subtraction we get numbers which are not multiple of p or q.
@arjun sir

can you please explain it a bit more, actually not getting it.
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
Got it. Thanx
Maybe you want to tell that you have used Inclusion - Exclusion Theorom
+5 votes

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)

so D is the answer

answered by Boss (6k points)  

Please provide derivation of ∅(p2). 

+5 votes

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)...(P_k-1)}{P_1 P_2..P_k} )$

$\text{where } P_1 P_2..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*}$


 

answered by Veteran (20.2k points)  
–3 votes
1 is the answer
answered by (465 points)  
reshown by
how?


Top Users Apr 2017
  1. akash.dinkar12

    3366 Points

  2. Divya Bharti

    2536 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1584 Points

  8. Prashant.

    1462 Points

  9. Arunav Khare

    1444 Points

  10. Kapil

    1414 Points

Monthly Topper: Rs. 500 gift card

22,072 questions
28,030 answers
63,194 comments
24,128 users