GATE CSE
First time here? Checkout the FAQ!
x
+9 votes
588 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 (20k points)  
edited by | 588 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 (291k 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
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
+7 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 (21.1k points)  
+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 (6.2k points)  

Please provide derivation of ∅(p2). 

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


Top Users Aug 2017
  1. Bikram

    5388 Points

  2. ABKUNDAN

    4730 Points

  3. manu00x

    3582 Points

  4. akash.dinkar12

    3534 Points

  5. rahul sharma 5

    3196 Points

  6. makhdoom ghaya

    2710 Points

  7. just_bhavana

    2432 Points

  8. stblue

    2244 Points

  9. Tesla!

    2126 Points

  10. pawan kumarln

    1914 Points


25,076 questions
32,240 answers
75,170 comments
30,249 users