Assuming that d divides n, prove that Φ(d) divides Φ(n)
hint; work with the prime factorization of d and n
Printable View
Assuming that d divides n, prove that Φ(d) divides Φ(n)
hint; work with the prime factorization of d and n
Use the fact that $\displaystyle \phi(n)=n\prod_{p\mid n}(1-p^{-1})$. What can you say about $\displaystyle \phi(n)/\phi(d)$ using this?
Suppose $\displaystyle d = p_1^{\alpha_1}p_2^{\alpha_2}\cdot\cdot\cdot p_k^{\alpha_k} $ and $\displaystyle n = p_1^{\beta_1}p_2^{\beta_2}\cdot\cdot\cdot p_k^{\beta_k}p_{k+1}^{\beta_{k+1}} \cdot\cdot\cdot p_r^{\beta_r} $ where $\displaystyle p_1 $ through $\displaystyle p_k $ are the same for both $\displaystyle d $ and $\displaystyle n $.
Note $\displaystyle \beta_i \geq \alpha_i $.
$\displaystyle \phi(n) = \phi(p_1^{\beta_1}p_2^{\beta_2}\cdot\cdot\cdot p_k^{\beta_k})\phi(p_{k+1}^{\beta_{k+1}} \cdot\cdot\cdot p_r^{\beta_r}) = C \cdot p_1^{\beta_1-1}p_2^{\beta_2-1}\cdot\cdot\cdot p_k^{\beta_k-1}(p_1-1)(p_2-1)\cdot\cdot\cdot(p_k-1) $
$\displaystyle \phi(d) = \phi(p_1^{\alpha_1}p_2^{\alpha_2}\cdot\cdot\cdot p_k^{\alpha_k}) = p_1^{\alpha_1-1}p_2^{\alpha_2-1}\cdot\cdot\cdot p_k^{\alpha_k-1}(p_1-1)(p_2-1)\cdot\cdot\cdot(p_k-1) $
Now just match up terms to see indeed $\displaystyle \phi(d) \mid \phi(n) $.
