Results 1 to 6 of 6

Thread: 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; Mar 6th 2008 at 03: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
    10
    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
    10
    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
    10
    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: Mar 23rd 2010, 06:20 PM
  2. prove,,,
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 1st 2010, 10:02 AM
  3. Prove |w + z| <= |w| +|z|
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Feb 28th 2010, 06:44 AM
  4. Replies: 2
    Last Post: Aug 28th 2009, 03:59 AM
  5. How to prove that n^2 + n + 2 is even??
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Nov 30th 2008, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum