Results 1 to 9 of 9

Math Help - [SOLVED] Number Theory:Euler phi function proofs

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    7

    [SOLVED] Number Theory:Euler phi function proofs

    1) show that if d does not equal m and d is a divisor of m then phi(d) divides phi(m).

    2)show that for any positive integer m and n, phi(m)*phi(n)=phi(gcd(m,n))*phi(lcm(m,n)).


    I just don't know where to begin so a push in the right direction would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    For n = \Pi_i p_i^{\alpha_i}, with p_i\neq p_j, if\ i\neq j and are prime numbers

    \varphi(n) = \Pi_i(p_i-1)p_i^{\alpha_i - 1}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Willie_Trombone View Post
    1) show that if d does not equal m and d is a divisor of m then phi(d) divides phi(m).

    2)show that for any positive integer m and n, phi(m)*phi(n)=phi(gcd(m,n))*phi(lcm(m,n)).


    I just don't know where to begin so a push in the right direction would be greatly appreciated.
    have you considered the formulas for \varphi (n) for some integer n? the idea for the proofs should be evident after that
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2009
    Posts
    7
    okay I got the first one but the second is still giving me trouble.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    Quote Originally Posted by Willie_Trombone View Post
    okay I got the first one but the second is still giving me trouble.
    Show first that for m,n relatively prime \varphi(mn) = \varphi(m)\varphi(n)

    Now, notice \frac{m}{\textrm{gcd}(m,n)} and n are relatively prime for any m,n and use the first result and the relation between gcd and lcm.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Feb 2009
    Posts
    7
    can \phi(m/gcd(m,n)) be expressed as \phi(m)/\phi(gcd(m,n))?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    Quote Originally Posted by Willie_Trombone View Post
    can \phi(m/gcd(m,n)) be expressed as \phi(m)/\phi(gcd(m,n))?

    Yes, the division is well defined by the question 1) and you can use the fact that \frac{m}{\mathrm{gcd}(m,n)} and gcd(m,n) are relatively prime and distribute \varphi
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Feb 2009
    Posts
    7
    thanks so much, I got it now.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    Quote Originally Posted by Willie_Trombone View Post
    thanks so much, I got it now.
    good to know it helped
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's Φ Function Proofs
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 9th 2010, 09:01 PM
  2. Replies: 0
    Last Post: February 20th 2010, 08:26 AM
  3. σ number theory proofs?
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 30th 2009, 08:30 AM
  4. Number theory integer proofs
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 10th 2009, 09:45 PM
  5. [SOLVED] GCD Proof: Elem. Number Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 9th 2009, 01:50 AM

Search Tags


/mathhelpforum @mathhelpforum