Results 1 to 12 of 12
Like Tree3Thanks
  • 1 Post By ignite
  • 1 Post By ILikeSerena
  • 1 Post By Moo

Math Help - Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    Suppose m and n are relatively prime positive integers; show that
    m^{\phi(n)} + n^{\phi(m)} \equiv 1 \pmod{mn}
    where \phi is the Euler Totient function.

    I can only see that \phi(mn) = \phi(m) \phi(n) because gcd(m,n) = 1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member ignite's Avatar
    Joined
    Apr 2012
    From
    Kanpur,India
    Posts
    54
    Thanks
    12

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    Quote Originally Posted by math2011 View Post
    Suppose m and n are relatively prime positive integers; show that
    m^{\phi(n)} + n^{\phi(m)} \equiv 1 \pmod{mn}
    where \phi is the Euler Totient function.

    I can only see that \phi(mn) = \phi(m) \phi(n) because gcd(m,n) = 1.
    Since (m,n)=1 ,we can find k and l such that  km+ln=1  (Using Extended Euclid's Theorem)
    Also using Euler's Theorem,  m^{\phi(n)} \equiv 1 \pmod{n} and  n^{\phi(m)} \equiv 1 \pmod{m}
    Can you use the above two facts and take it from there?If not,I will further elaborate.
    Thanks from math2011
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    Are you aware of the Chinese remainder theorem?
    It fits kind of neatly, since it says there's a natural isomorphism between (mod mn) and the combination of (mod m) and (mod n).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    Thank you for your replies. However, I cannot figure out the rest of the solution from either of your hints. Could you please elaborate?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    The Chinese remainder theorem says that the function
    f: Z/mnZ \to Z/mZ x Z/nZ
    given by
    (x mod mn) \mapsto (x mod m, x mod n)
    is an isomorphism if m and n are relatively prime.

    Please give some feedback on what you know or do not know, or perhaps what you've tried.

    Pick x=m^{\phi(n)} + n^{\phi(m)}.
    Last edited by ILikeSerena; April 29th 2012 at 08:50 AM.
    Thanks from math2011
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    I can solve it now. Thank you for your help.

    x=m^{\phi(n)} + n^{\phi(m)}

    From x \equiv 1 \pmod{m} we have
    x = 1 + my.
    Substitute into x \equiv 1 \pmod{n} we get
    1 + my \equiv 1 \pmod{n}.
    which simplies to
    my \equiv 0 \pmod{n}.
    Solve y to get
    y \equiv 0 \pmod{n},
    y = nz.
    Substitute back into first equation to get
    x = 1 + mnz.
    Hence:
    x \equiv 1 \pmod{mn}.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    Hmm, I can't follow what you did there (without making a great effort).

    I'll just show my proof (using the definition of f from my previous post):
    x \mod m \equiv m^{\phi(n)} + n^{\phi(m)} \mod m \equiv 1 \mod m
    x \mod n \equiv m^{\phi(n)} + n^{\phi(m)} \mod n \equiv 1 \mod n

    Therefore:
    f: (x \mod {mn}) \mapsto (1 \mod m, 1 \mod n)

    Since we also have from the definition of f:
    f: (1 \mod {mn}) \mapsto (1 \mod m, 1 \mod n)

    and since f is bijective (it's an isomorphism), it follows that
    x \mod {mn} \equiv 1 \mod {mn}

    \square
    Last edited by ILikeSerena; April 30th 2012 at 08:51 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    Did you mean that the definition of f is f : (x \pmod{mn}) \to (x \pmod{m}, x \pmod{n})? Why is this a bijective function? Do we need to prove that it is a bijective function?

    P.S. The method I used is one of the methods for solving simultaneous congruences.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    Quote Originally Posted by math2011 View Post
    Did you mean that the definition of f is f : (x \pmod{mn}) \to (x \pmod{m}, x \pmod{n})? Why is this a bijective function? Do we need to prove that it is a bijective function?

    P.S. The method I used is one of the methods for solving simultaneous congruences.
    Yes it is.
    The function f is bijective because the Chinese remainder theorem says so.

    Do we need to prove it?
    I don't know.
    That depends on your context.
    You have not set any boundaries on what you can or cannot use.

    The Chinese remainder theorem also says exactly how you can solve a simultaneous set of congruences.
    See for instance this link for a simple formula.
    Last edited by ILikeSerena; May 1st 2012 at 03:21 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    Thank you for helping me with this problem. I really appreciate it.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    You're welcome.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6

    Re: Suppose gcd(m,n)=1, show that m^{phi(n)} + n^{phi(m)} = 1 (mod mn)

    Hello,

    Another way : modular arithmetic
    Thanks from ILikeSerena
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Suppose E[Y|X]=1. Show Cov(Y,X)=0.?
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 18th 2011, 04:03 AM
  2. Suppose |G|=22. Show G has elements of order 2 and 11.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 14th 2011, 02:49 PM
  3. Replies: 6
    Last Post: March 2nd 2011, 01:36 AM
  4. Suppose that g(t)...
    Posted in the Calculus Forum
    Replies: 4
    Last Post: November 5th 2009, 02:27 PM
  5. Suppose that...
    Posted in the Calculus Forum
    Replies: 0
    Last Post: October 13th 2009, 02:10 PM

Search Tags


/mathhelpforum @mathhelpforum