Prove that if $d$ divides $n$ then $φ(d)$ divide $φ(n)$ for $φ$ denotes Euler’s φ-function.

Solution 1:

It is true for $\rm\color{#0a0}{prime\ powers}$, so for all naturals, because $\phi$ is $\color{#c00}{\rm multiplicative},$ i.e. $\,\phi(ab) = \phi(a)\phi(b)\,$ for coprime $a,b,\,$ therefore $\ \phi(p_1^{n_1}\cdots p_k^{n_k}) = \phi(p_1^{n_1})\cdots \phi(p_k^{n_k})\,$ for distinct primes $\,p_i$. Explicitly

$$\begin{eqnarray} &&\qquad\qquad\qquad\ \ \ p^i \cdots q^j\ \mid\ p^I\cdots q^J\quad\ {\rm for\ distinct\ primes}\ \ p,\ldots, q \\ \Rightarrow\ &&\qquad \quad\ \ \color{#0a0}{p^i\mid p^I},\qquad\quad\ \ldots,\qquad\quad \ \ q^j\mid q^J \\ \Rightarrow\ &&\color{#0a0}{(p\!-\!1)p^{i-1}\mid (p\!-\!1)p^{I-1}},\ldots,(q\!-\!1)q^{j-1}\mid (q\!-\!1)q^{J-1} \\ \Rightarrow\ &&\qquad\ \color{#0a0}{\phi(p^i)\mid \phi(p^I)},\qquad\ldots,\qquad\,\phi(q^j)\mid\phi(q^J)\\ \Rightarrow\ &&\qquad\qquad\ \, \phi(p^i)\cdots\phi(q^j)\mid \phi(p^I)\cdots\phi(q^J)\\ \Rightarrow\ &&\qquad\qquad\qquad\!\phi(p^i\cdots q^j)\mid \phi(p^I\cdots q^J)\quad\ \ \rm by\ \phi\ is\ \color{#c00}{multiplicative} \end{eqnarray}$$

Remark $\,\ $ Similarly, generally a "multiplicative" statement about a multiplicative function is true if it is true for prime powers.

Solution 2:

Lemma1: $\phi(n)=n\prod_{p|n}(1-1/p)$

Lemma2: $\phi(mn)=\phi(m)\phi(n)\dfrac{d}{\phi(d)}$, where $d=(m,n)$. (Deduced from Lemma 1)

Since $a|b$ we have $b=ac$ where $1 \leq c \leq b$. If $c=b$ then $a=1$ and $\phi(a)|\phi(b)$ is trivially satisfied. Therefore, assume $c<b$. From Lemma2 we have $\phi(b)=\phi(ac)=\phi(a)\phi(c)\dfrac{d}{\phi(d)}=d\phi(a)\dfrac{\phi(c)}{\phi(d)}(*)$

where $d=(a,c)$. Now the result follows by induction on $b$. For $b=1$ it holds trivially. Suppose, then, it holds for all integers $<b$. Then it holds for $c$ so $\phi(d)|\phi(c)$ since $d|c$. Hence the right member of (*) is a multiple of $\phi(a)$ which means $\phi(a)|\phi(b)$. This proves the assertion.