How can I show that $\phi(m) \mid \phi(n)$?

Question

I want to prove that:

$$\text{ if } m,n \geq 1 \text{ and } m \mid n,\text{ then } \phi(m) \mid \phi(n).$$

How can I show this?

I thought the following:

$$m \mid n \Rightarrow \exists k \in \mathbb{Z} \text{ such that } n=km$$

$$\text{We write } m \text{ like that : }m=p_1^{a_1} \cdots p_k^{a_k}, \text{ where } p_i \text{ are primes and } a_i>0$$

Then,we have $n=k p_1^{a_1} \cdots p_k^{a_k}$

We could show that $\phi(m) \mid \phi(n)$,using the fact that as $\phi$ is multiplicative and if $(m,n)=1$ ,then $\phi(mn)=\phi(m) \phi(n)$

But..it is possible that $k \mid p_1^{a_1 \cdots p_k^{a_k}}$.

So,do I have to show maybe that $\gcd(kp_1^{a_1} \cdots p_{k-1}^{a_{k-1}},p_k^{a_k})=1$ ?

Answer 1

You could use the fact that if $n = p_1^{a_1}\ldots p_k^{a_k}$ then $\phi(n) = (p_1 - 1)p_1^{a_1 -1}\ldots (p_k - 1)p_k^{a_k -1}$

Answer 2

If the highest power of prime $p_i$ in $m,n$ are $M_i,N_i$ respectively, $0\le M_i\le N_i$ for all $i$

Now for each $M_i>0,$ $$\displaystyle\phi(m)=\prod\phi(p_i^{M_i})=\prod p^{M_i-1}(p_i-1)$$

and similarly for each $N_i>0,$ $$\displaystyle\phi(n)=\prod\phi(p_i^{N_i})=\prod p^{N_i-1}(p_i-1)$$

$\displaystyle p^{M_i-1}$ clearly divides $p^{N_i-1}$ for all $i$ as $M_i\le N_i$ for all $i$

So, the proposition follows

Answer 3

Here is a more conceptual viewpoint, which is not how you are thinking about the problem, but I think it provides a nice explanation for the result without grinding out formulas for the $\varphi$-function. You need to know some abstract algebra to makes sense of what is below, or this may be some motivation to learn it.

Since $m|n$, there is a natural reduction map ${\mathbf Z}/n{\mathbf Z} \rightarrow {\mathbf Z}/m{\mathbf Z}$, given by $a \bmod n \mapsto a \bmod m$, which is a ring homomorphism. It is obviously surjective. This ring homomorphism induces a homomorphism on the unit groups $(\mathbf Z/n\mathbf Z)^\times \rightarrow (\mathbf Z/m\mathbf Z)^\times$. Prove, less obviously, that this map between unit groups is surjective. (Hint: think about the Chinese remainder theorem, if you know what that is.) Then you are done, since if there is a surjective homomorphism between finite groups $H \rightarrow G$ then necessarily $|G|$ divides $|H|$.

The basic point is that if you are trying to show one positive integer $a$ divides another positive integer $b$, you might try to explain it with group theory: find a finite group $G$ with order $a$ and a finite group $H$ with order $b$, and either construct an injective group homomorphism $G \rightarrow H$ or a surjective group homomorphism $H \rightarrow G$. Either way it would follow that $a$ divides $b$ (by Lagrange's theorem for the injective case, and by quotient groups and the first homomorphism theorem in the surjective case). In your problem $a = \varphi(m)$ and $b = \varphi(n)$, which are the orders of the unit groups mod $m$ and mod $n$.

Answer 4

We have $$ \phi(n)=n\prod_{p\mid n}\left(1-\frac1p\right) $$ $$ \phi(m)=m\prod_{p\mid m}\left(1-\frac1p\right) $$

Now $m\mid n$ implies that the set of primes $p\mid m$ is a subset of the primes $p\mid n$. Hence $\phi(n)/\phi(m)$ is an integer because the factors corresponding to the common primes cancel and the denominators of the other factors are cancelled by $n$.

Answer 5

Since $\phi$ is a multiplicative function, this question reduced to the case where $n,m$ are powers of the same prime. Since $\phi(p^k)=(p-1)^{\min(k,1)}p^{\max(k,1)-1}$, where both $k\mapsto\min(k,1)$ and $k\mapsto\max(k,1)-1$ are increasing functions $\Bbb N\to\Bbb N$, the result holds in the mentioned case.