Results 1 to 3 of 3

Math Help - Euler phi function proof

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    24

    Euler phi function proof

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

    hint; work with the prime factorization of d and n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    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) .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Euler function proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 23rd 2011, 08:44 AM
  2. Euler's totient function Proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 10th 2011, 05:30 AM
  3. Euler Function Proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 5th 2011, 12:04 AM
  4. Proof about Euler's φ-function
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: September 28th 2010, 01:13 PM
  5. Euler's phi function proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 7th 2010, 08:46 PM

Search Tags


/mathhelpforum @mathhelpforum