# Thread: Euler phi function proof

1. ## Euler phi function proof

Assuming that d divides n, prove that Φ(d) divides Φ(n)

hint; work with the prime factorization of d and n

2. Use the fact that $\phi(n)=n\prod_{p\mid n}(1-p^{-1})$. What can you say about $\phi(n)/\phi(d)$ using this?

3. Suppose $d = p_1^{\alpha_1}p_2^{\alpha_2}\cdot\cdot\cdot p_k^{\alpha_k}$ and $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 $p_1$ through $p_k$ are the same for both $d$ and $n$.

Note $\beta_i \geq \alpha_i$.

$\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)$

$\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 $\phi(d) \mid \phi(n)$.