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

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

I know that $d|n$ mean there exists some integer $k$ such that $n=kd$, but how can I use this to prove $φ(d)$ divide $φ(n)$

• Why use the abstract algebra tag rather than the number theory tag? – Ayesha Jan 11 '14 at 15:06
• this problem is from abstract algebra class :D – Diane Vanderwaif Jan 11 '14 at 15:10

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.

• See here for a proof of Lemma 2 $\$ – Bill Dubuque Jun 12 '16 at 15:58

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.

Hint: Use that if $p$ and $q$ are primes you have $$\varphi(p\cdot q) = \varphi(p)\cdot \varphi(q)$$

You can use the formula $$\text{If } n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}\Rightarrow \phi(n)=p_1^{a_1-1}p_2^{a_2-1}\cdots p_r^{a_r-1} \left(p_1-1\right) \left(p_2-1\right)\cdots\left(p_r-1\right).$$

You may know that $\phi(pd)=p\phi(d)$ and $\phi(pd)=(p-1)\phi(d)$ if $p\not\mid d$ (where $p$ is a prime).

• can you explain a little more, I still can't see how this can help me prove that statement. – Diane Vanderwaif Jan 11 '14 at 15:55