Exercise 2.5.3 (If $d\mid m$, then $\phi(d) \mid \phi(m)$)

Question

Show that if $d\mid m$ then $\phi(d) \mid \phi(m)$.

Richard Ganaye · Accepted Answer

\begin{proof} 
If $d = 1$, $\phi(d) = 1 \mid \phi(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*}
\phi(m) & = \prod_{i\in I} p_i^{a_i-1} (p_i-1),\
\phi(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$, $\phi(d) \mid \phi(n)$.
\end{proof}

Exercise 2.5.3 (If $d\mid m$, then $\phi(d) \mid \phi(m)$)

Answers

Comments

Exercise 2.5.3 (If $d\mid m$, then $\phi(d) \mid \phi(m)$)

Answers

Comments

Add answer