Euler phi function proof

**MichaelG** · November 29th 2009, 09:24 PM

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

hint; work with the prime factorization of d and n

**Bruno J.** · November 29th 2009, 09:56 PM

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?

**chiph588@** · November 29th 2009, 09:58 PM

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

Thread: Euler phi function proof

LinkBack

Thread Tools

Display

Euler phi function proof

Similar Math Help Forum Discussions

[SOLVED] Euler function proof

Euler's totient function Proof

Euler Function Proof

Proof about Euler's φ-function

Euler's phi function proof

Search Tags