# Euler phi function proof

• Nov 29th 2009, 09:24 PM
MichaelG
Euler phi function proof
Assuming that d divides n, prove that Φ(d) divides Φ(n)

hint; work with the prime factorization of d and n
• Nov 29th 2009, 09:56 PM
Bruno J.
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?
• Nov 29th 2009, 09:58 PM
chiph588@
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)$.