# How many numbers $m$ satisfy $1 ≤ m ≤ n$ and $\gcd (m, n) = 1$?

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.

• Your attempt is fine. – almagest Apr 13 '16 at 11:58
• explain what ? that $\phi(p^2 q) = \phi(p^2) \phi(q)$ ? – reuns Apr 13 '16 at 11:59
• 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)$. – lulu Apr 13 '16 at 12:01

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)$$
• 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. – lulu Apr 13 '16 at 13:19