Results 1 to 9 of 9

Math Help - Euler phi

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    11

    Euler phi

    Show that a^{\phi(b)}+b^{\phi(a)} \equiv 1 \pmod{ab} if a and b are relatively prime.

    Starting with a and b are relatively prime I get

    a^{\phi(b)} \equiv 1 \pmod{b}<br />
    <br />
b^{\phi(a)} \equiv 1 \pmod{a}<br />

    But I am not sure how to combine the moduli to get \pmod{ab}. Would Chinese Remainder Theorem be the right approach?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by RonyPony View Post
    Show that a^{\phi(b)}+b^{\phi(a)} \equiv 1 \pmod{ab} if a and b are relatively prime.

    Starting with a and b are relatively prime I get

    a^{\phi(b)} \equiv 1 \pmod{b}<br />
    <br />
b^{\phi(a)} \equiv 1 \pmod{a}<br />

    But I am not sure how to combine the moduli to get \pmod{ab}. Would Chinese Remainder Theorem be the right approach?
     \begin{cases} a^{\varphi(b)}-1 \equiv 0 \bmod{b}\\b^{\varphi(a)}-1 \equiv 0 \bmod{a}\end{cases}\implies (a^{\varphi(b)}-1)(b^{\varphi(a)}-1)\equiv0 \bmod{ab} as  (a,b)=1


    But  0\equiv(a^{\varphi(b)}-1)(b^{\varphi(a)}-1)=a^{\varphi(b)}b^{\varphi(a)}-a^{\varphi(b)}-b^{\varphi(a)}+1=ab\left\{a^{\varphi(b)-1}b^{\varphi(a)-1}\right\}-a^{\varphi(b)}-b^{\varphi(a)}+1

     \equiv-a^{\varphi(b)}-b^{\varphi(a)}+1\bmod{ab}
    Last edited by chiph588@; July 6th 2010 at 05:09 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2010
    Posts
    11
    Quote Originally Posted by chiph588@ View Post
     \implies (a^{\varphi(b)}-1)(b^{\varphi(a)}-1)\equiv0 \bmod{ab} as  (a,b)=1
    Why are we allowed to do this step?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by RonyPony View Post
    Why are we allowed to do this step?
    Actually that step is wrong... Try this:

     a^{\varphi(b)}\equiv1\bmod{b}\implies a^{\varphi(b)}+b^{\varphi(a)}\equiv1\bmod{b}

     b^{\varphi(a)}\equiv1\bmod{a}\implies b^{\varphi(a)}+a^{\varphi(b)}\equiv1\bmod{a}

    Since  (a,b)=1 ,  a^{\varphi(b)}+b^{\varphi(a)}\equiv1\bmod{ab}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Is the last step is from Chinese remainder theorem?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Also sprach Zarathustra View Post
    Is the last step is from Chinese remainder theorem?
    See this page on MathWorld, property #11. Note that \gcd(a,b) = 1 \implies \text{lcm}(a,b)=ab.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Also sprach Zarathustra View Post
    Is the last step is from Chinese remainder theorem?
     x\equiv y\bmod{n} and  x\equiv y\bmod{m} where  (n,m)=1\implies x\equiv y\bmod{nm}

    This is because  x=y+nk and  x=y+mj \implies nk=mj\implies m\mid nk\implies m\mid k since  (n,m)=1 .

    This means  k=mr . Thus  x=y+nmr\implies x\equiv y\bmod{nm} .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by chiph588@ View Post
    \implies (a^{\varphi(b)}-1)(b^{\varphi(a)}-1)\equiv0 \bmod{ab}
    You said this step is wrong, why?
    If a|c and b|d, then ab|cd regardless, even, of a and b being relatively prime. Here, a and b divide b^{\varphi(a)}-1 and a^{\varphi(b)}-1, respectively. Then ab|(b^{\varphi(a)}-1)(a^{\varphi(b)}-1).
    Is it correct?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by melese View Post
    You said this step is wrong, why?
    If a|c and b|d, then ab|cd regardless, even, of a and b being relatively prime. Here, a and b divide b^{\varphi(a)}-1 and a^{\varphi(b)}-1, respectively. Then ab|(b^{\varphi(a)}-1)(a^{\varphi(b)}-1).
    Is it correct?
    Yes you are correct. I had a lapse in clear thought for a bit. Thanks for pointing that out.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 09:18 PM
  2. Replies: 0
    Last Post: February 20th 2010, 09:26 AM
  3. Replies: 0
    Last Post: September 17th 2009, 07:44 PM
  4. euler phi-function
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 29th 2009, 08:42 PM
  5. Euler Phi Help
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 28th 2008, 01:53 PM

Search Tags


/mathhelpforum @mathhelpforum