Results 1 to 2 of 2

Math Help - Euler's Phi Function

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    30

    Euler's Phi Function

    Prove that if the integer n has r distinct odd prime factors, then 2^r |
    Ф(n).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Suppose n \geq 3 has r odd prime factors.

    By definition, we have: \phi (n) = n \cdot \prod_{p \mid n} \left(\frac{p-1}{p}\right) = \frac{n}{\displaystyle \prod_{p \mid n} p} \cdot \prod_{p \mid n} (p-1)

    We know that the fraction is an integer and that since p is prime, then p-1 is even. So for every odd prime dividing n, there is a corresponding even number (particularly p-1) that divides \phi (n). Since there are r odd primes, the conclusion follows.
    Last edited by o_O; March 26th 2009 at 07:07 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler function
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 30th 2011, 10:53 AM
  2. Euler Function phi(n)
    Posted in the Number Theory Forum
    Replies: 22
    Last Post: May 29th 2010, 08:29 AM
  3. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 8th 2010, 03:58 PM
  4. Euler's phi function
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: January 12th 2010, 06:10 AM
  5. Euler phi-Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 11th 2009, 07:11 PM

Search Tags


/mathhelpforum @mathhelpforum