Monday, 9 February 2026

Exercise (5.1).18

Let $d$ be a positive divisor of $n$, that is $d \mid n$. Prove that

$$ \phi (d) \; \mid \; \phi (n)$$

Hint: Consider the prime decompositions of $d$ and $n$.


We're given $d \mid n$ and so every prime $p_i$ that appears in prime decomposition of $d$ also appears in the prime decomposition of $n$, raised to the same or higher power.

If we decompose $d$ as follows, with $p_i$ as distinct primes, and $k_i \ge 1$ natural numbers

$$ d = \prod_{i=1}^{r}p_i^{k_i} $$

then we can decompose $n$ as

$$ n = m \times \prod_{i=1}^{r}p_i^{k_i+j_i} $$

where $j_i \ge 0$, and $m$ is the remaining factor which contains no primes $p_i$. 


We now consider $\phi(d)$ and $\phi(n)$, making use of $m$ being coprime to any power of $p_i$ to use the multiplicity of $\phi$.

$$ \begin{align} \phi(d) & = \textcolor{Red}{\prod_{i=1}^{r} p_i^{k_i-1}(p-1)} \\ \\  \phi(n) & = \phi(m) \times  \prod_{i=1}^{r} p_i^{k_i + j_i -1}(p_i -1)  \\ \\ & = \phi(m) \times \textcolor{Red}{\prod_{i=1}^{r} p_i^{k_i -1}(p_i -1)} \times  p_i^{j_i} \end{align} $$


We can see $\phi(d)$ appears as a factor of $\phi(n)$ and so we can conclude

$$ \phi (d) \; \mid \phi (n) $$