edited by
7,972 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

1 votes
1 votes
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
0 votes
0 votes

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

Answer:

Related questions

44 votes
44 votes
10 answers
1
22 votes
22 votes
3 answers
3
Ishrat Jahan asked Oct 29, 2014
7,262 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,982 views
The exponent of $11$ in the prime factorization of $300!$ is$27$$28$$29$$30$