Let $n = p^2 q$ where $p$ and $q$ are distinct prime numbers. How many numbers $m$ satisfy $1 \leq m \leq 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. $(p^2- 1) (q - 1)$
  4. $p(p - 1) (q - 1)$

My attempt:

Using prime factorization :

Eulers function is $\phi(p^n)$ is $p^{n-1}(p-1)$

given that $n=p^2q(p,q$ prime$)$

$\phi(p^2q)=\phi(p^2)*\phi(q) =p(p-1)(q-1)$

Can you explain in alternative/formal way? Please.

  • $\begingroup$ Your attempt is fine. $\endgroup$ – almagest Apr 13 '16 at 11:58
  • 1
    $\begingroup$ explain what ? that $\phi(p^2 q) = \phi(p^2) \phi(q) $ ? $\endgroup$ – reuns Apr 13 '16 at 11:59
  • 1
    $\begingroup$ As an alternate method: there are $pq$ numbers in the range which are divisible by $p$, $p^2$ which are divisible by $q$, and $p$ which are divisible by both. Hence by the Principle of Inclusion/Exclusion we get $p^2q-pq-p^2+p=p(p-1)(q-1)$. $\endgroup$ – lulu Apr 13 '16 at 12:01

as requested in the comments:

We can do this via the Principle of Inclusion/Exclusion.

There are exactly $pq$ numbers $1≤m≤p^2q$ which are divisible by $p$.

There are exactly $p^2$ which are divisible by $q$.

There are exactly $p$ which are divisible by both $p$ and $q$.

Thus: $$\varphi(p^2q)=p^2q-pq-p^2+p=p(p-1)(q-1)$$

  • $\begingroup$ No problem. Actually, you can derive the closed formula for $\varphi (n)$ this way, for any $n$ (given the factoring). Not my favorite method....the multiplicativity of $\varphi$ is a very important property and worth understanding directly. $\endgroup$ – lulu Apr 13 '16 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.