Results 1 to 2 of 2

Math Help - Euler phi-function

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    21

    Euler phi-function

    Let n be a positive integer having k distinct odd prime divisors. Prove that 2^k divides Euler phi-function(n).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Suppose  n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\cdot\cdot p_k^{\alpha_k} where  p_i \neq 2 .

    Then  \phi(n) = \phi(p_1^{\alpha_1})\cdot\phi(p_2^{\alpha_2})\cdot  \cdot\cdot\phi(p_k^{\alpha_k}) .

    Note that  \phi(p_i^{\alpha_i})=p_i^{\alpha_i-1}\cdot (p_i-1) .

    So we have  2 \mid p_i-1 \; \forall i \implies 2^k \mid \phi(n) .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler Phi function II
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 27th 2009, 04:33 AM
  2. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 16th 2008, 05:54 PM
  3. Euler's Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 02:52 PM
  4. euler phi function and others
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 4th 2008, 05:43 PM
  5. Help with euler-phi function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 1st 2007, 06:42 PM

Search Tags


/mathhelpforum @mathhelpforum