Results 1 to 6 of 6

Math Help - Prove

  1. #1
    Member
    Joined
    Feb 2008
    Posts
    125

    Prove

    If m and n are natural numbers, prove that m^(2*n) is congruent to 1(mod m+1)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

    I'm sure that there is a better way, but I think this works.

    Quote Originally Posted by mandy123 View Post
    If m and n are natural numbers, prove that m^(2*n) is congruent to 1(mod m+1)
    We need to show that (m+1)|(m^{2n}-1)

    rewriting we get...

    (m+1)|(m^n-1)(m^n+1)


    so it is sufficient to show m+1 divides either of them...

    define q

    q=\sum_{i=0}^{n-1}(-1)^im^{(n-1)-i}

    so multiplying (m+1)q we get...

    (m+1) \cdot \sum_{i=0}^{n-1}(-1)^im^{(n-1)-i}=\left(\sum_{i=0}^{n-1}(-1)^im^{(n)-i}\right)+\sum_{i=0}^{n-1}(-1)^im^{(n-1)-i}

    By telescoping the sum we get..

    m^n+1 if n is odd or

    m^n-1 if n is even.

    Then we get...

    (m+1)q=m^n+1 or (m+1)q=m^n-1

    This show s that


    (m+1)|(m^n+1) or (m+1)|(m^n-1)

    Last edited by TheEmptySet; March 6th 2008 at 02:17 PM. Reason: to be clearer
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Note, if k is odd then x^k + 1 = (x+1)(x^{k-1} - x^{k-2}+...-x+1),

    We need to show (m+1)|(m^{2n}-1). Thus, (m+1)|(m^n-1)(m^n+1). If n is odd then m^n+1 is divisible by m+1 and use the result above. If n is even then m^n - 1 = (m^{n/2} - 1)(m^{n/2}+1). Now if n/2 is odd then m+1 is a factor by above result. Otherwise it is even and then factor m^{n/2} - 1 = (m^{n/4} - 1)(m^{n/4} + 1) and apply the same argument. Since we cannot go indefinitely it means at some point n/2^i is odd and at that point m^{n/2^i}+1 has m+1 as a factor,
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by mandy123 View Post
    If m and n are natural numbers, prove that m^(2*n) is congruent to 1(mod m+1)
    To show that m+1 divides f(m) = m^{2n} - 1, you can use the factor theorem. This says that m+1 will be a factor of f(m) if f(1)=0. But that is obvious, since (-1)^{2n}=1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    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 Opalg View Post
    To show that m+1 divides f(m) = m^{2n} - 1, you can use the factor theorem. This says that m+1 will be a factor of f(m) if f(1)=0. But that is obvious, since (-1)^{2n}=1.
    after looking at the other solutions, this one is nice and concise! but question: doesn't the fact that m and n are natural numbers mean we cannot have m = -1, which is what you seem to be saying, or is there something i am missing?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Jhevon View Post
    after looking at the other solutions, this one is nice and concise! but question: doesn't the fact that m and n are natural numbers mean we cannot have m = -1, which is what you seem to be saying, or is there something i am missing?
    Perhaps it will make it clearer if I modify the notation slightly. The factor theorem holds for the ring of polynomials with integer coefficients, so it applies to the polynomial f(x) = x^{2n}-1. Since f(–1)=0, it follows that x^{2n}-1 = (x+1)g(x) for some polynomial g(x) with integer coefficients. Now we can put x=m, to get m^{2n}-1 = (m+1)g(m), and therefore m+1 divides m^{2n}-1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a/b and a/c then a/ (3b-7c)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 23rd 2010, 05:20 PM
  2. prove,,,
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 1st 2010, 09:02 AM
  3. Prove |w + z| <= |w| +|z|
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 28th 2010, 05:44 AM
  4. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  5. How to prove that n^2 + n + 2 is even??
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 30th 2008, 01:24 PM

Search Tags


/mathhelpforum @mathhelpforum