Results 1 to 2 of 2

Math Help - euler's theorem 2nd question

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    29

    euler's theorem 2nd question

    Hi,

    i need to verify if my proof for this particular problem is correct.

    The theorem:

    Let m, n be relatively prime positive integers. Prove that m^Φ(n) + n^Φ(m) Ξ 0mod mn
    Proof:
    nx = m^Φ(n) – 1
    my = n^Φ(m) – 1
    Let xy = z
    nm(z) = (m^Φ(n) – 1)( n^Φ(m) – 1)
    nm(z) = m^Φ(n) n^Φ(m) - m^Φ(n) - n^Φ(m) + 1
    m^Φ(n) + n^Φ(m) - m^Φ(n) n^Φ(m) – 1 = (nm)(-z)
    m^Φ(n) n^Φ(m) Ξ 0mod (mn)
    Therefore,
    m^Φ(n) + n^Φ(m) Ξ 1mod (mn)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by htata123 View Post
    Hi,

    i need to verify if my proof for this particular problem is correct.

    The theorem:

    Let m, n be relatively prime positive integers. Prove that m^Φ(n) + n^Φ(m) Ξ 1mod mn
    Proof:
    nx = m^Φ(n) – 1
    my = n^Φ(m) – 1
    Let xy = z
    nm(z) = (m^Φ(n) – 1)( n^Φ(m) – 1)
    nm(z) = m^Φ(n) n^Φ(m) - m^Φ(n) - n^Φ(m) + 1
    m^Φ(n) + n^Φ(m) - m^Φ(n) n^Φ(m) – 1 = (nm)(-z)
    m^Φ(n) n^Φ(m) -1 Ξ 0mod (mn)
    Therefore,
    m^Φ(n) + n^Φ(m) Ξ 1mod (mn)
    Be careful, the correct statement is, if \text{gcd}(m,n)=1 then m^{\phi(n)}+n^{\phi(m)}\equiv{1}(\bmod.n\cdot m)

    But, besides that, your proof is correct . See in the quote above.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's theorem question finding the remainder...
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 22nd 2011, 03:55 AM
  2. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  3. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 5th 2009, 09:07 AM
  4. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: May 5th 2008, 04:19 PM
  5. Euler's theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 25th 2007, 12:53 PM

Search Tags


/mathhelpforum @mathhelpforum