Exercise 0.2.11 ($d \mid n \Rightarrow \varphi(d) \mid \varphi(n)$)

Question

Prove that if $d$ divides $n$, then $\varphi(d)$ divides $\varphi(n)$.

Richard Ganaye · Accepted Answer

(See Niven Ex. 2.5.3)
\begin{proof} 

If $d = 1$, $\varphi(d) = 1 \mid \varphi(m)$. If $d >1$, and $d \mid m$, we can write the decompositions of $d,m$ in prime factors:
\begin{align*}
m &= \prod_{i \in I} p_i^{a_i},\qquad a_i>0,\
d  &= \prod_{i \in J} p_i^{b_i},\qquad 0<b_i \leq a_i,
\end{align*}
where $J \subseteq I$.

Then
\begin{align*}
\varphi(m) & = \prod_{i\in I} p_i^{a_i-1} (p_i-1),\
\varphi(d) &= \prod_{j\in J} p_i^{b_i-1}(p_i-1).
\end{align*}
For every $i \in J$, $b_i \leq a_i$, thus $p_i^{b_i-1} \mid p_i^{a_i-1}$, so $p_i^{b_i-1}(p_i-1) \mid p_i^{a_i-1} (p_i-1)$. Since $J \subseteq I$, $\varphi(d) \mid \varphi(n)$.

\end{proof}

Exercise 0.2.11 ($d \mid n \Rightarrow \varphi(d) \mid \varphi(n)$)

Answers

Comments

Exercise 0.2.11 ($d \mid n \Rightarrow \varphi(d) \mid \varphi(n)$)

Answers

Comments

Add answer