edited by
7,954 views
31 votes
31 votes

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 by

7 Answers

Best answer
54 votes
54 votes
$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 by
64 votes
64 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)\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*}$

11 votes
11 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

2 votes
2 votes

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.

 

Answer:

Related questions

44 votes
44 votes
10 answers
1
22 votes
22 votes
3 answers
3
Ishrat Jahan asked Oct 29, 2014
7,255 views
The minimum positive integer $p$ such that $3^{p} \pmod {17} = 1$ is$5$$8$$12$$16$
14 votes
14 votes
3 answers
4
Ishrat Jahan asked Oct 27, 2014
7,967 views
The exponent of $11$ in the prime factorization of $300!$ is$27$$28$$29$$30$