Prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$.

Solution 1:

Since $\varphi$ is a multiplicative function, and since from $a_i\mid b_i$ for $i=1,\ldots,n$ it follows that $\prod_{i=1}^m a_i\mid \prod_{i=1}^m b_i$, one can reduce the question to the case where $d$ and $n$ are both powers of the same prime. But from the formula $\varphi(p^k)=(p-1)^{\min(k,1)}p^{\max(0,k-1)}$ when $p$ is prime, the result is easily checked for that case (both exponents increase weakly monotonically with$~k$).

Solution 2:

For variety,

"Reduction modulo $d$" is a surjective ring homomorphism $\mathbf{Z} / n \mathbf{Z} \to \mathbf{Z} / d \mathbf{Z}$. Therefore, it is also a group homomorphism on the groups of invertible elements in the rings.

If $G$ is a finite group and $H$ a normal subgroup, then $|G| = |H| \cdot |G/H|$; therefore, the number of invertible elements modulo $d$ -- i.e. $\varphi(d)$ -- is a divisor of the number of invertible elements modulo $n$ -- i.e. $\varphi(n)$.

Solution 3:

Try using this identity

$$\frac{\varphi{(n)}}{n} = \frac{\varphi{(p_1)}}{p_1}\cdot\frac{\varphi{(p_2)}}{p_2}\ldots$$

where $p_i$ is a prime factor of $n$