Results 1 to 9 of 9

Thread: [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 $\displaystyle n = \Pi_i p_i^{\alpha_i}$, with $\displaystyle p_i\neq p_j, if\ i\neq j$ and are prime numbers

    $\displaystyle \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
    5
    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 $\displaystyle \varphi (n)$ for some integer $\displaystyle 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 $\displaystyle \varphi(mn) = \varphi(m)\varphi(n)$

    Now, notice $\displaystyle \frac{m}{\textrm{gcd}(m,n)}$ and $\displaystyle 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 $\displaystyle \phi(m/gcd(m,n))$ be expressed as $\displaystyle \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 $\displaystyle \phi(m/gcd(m,n))$ be expressed as $\displaystyle \phi(m)/\phi(gcd(m,n))$?

    Yes, the division is well defined by the question 1) and you can use the fact that $\displaystyle \frac{m}{\mathrm{gcd}(m,n)}$ and $\displaystyle gcd(m,n)$ are relatively prime and distribute $\displaystyle \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: Apr 9th 2010, 09:01 PM
  2. Replies: 0
    Last Post: Feb 20th 2010, 08:26 AM
  3. σ number theory proofs?
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Nov 30th 2009, 08:30 AM
  4. Number theory integer proofs
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 10th 2009, 09:45 PM
  5. [SOLVED] GCD Proof: Elem. Number Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 9th 2009, 01:50 AM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum