Results 1 to 5 of 5

Math Help - Congruence Proofs: Summations

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    10

    Congruence Proofs: Summations

    Although I can prove these algebraically via induction, how are the following proved using modular arithmetic (where "=" means "congruent to")?

    1+2+...+(n-1)=0 mod n iff n is odd
    1^2+2^2+...+(n-1)^2=0 mod n iff n=+/-1 mod 6
    1^3+2^3+...+(n-1)^3=0 mod n iff n is not congruent to 2 mod 4

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by carabidus View Post
    Although I can prove these algebraically via induction, how are the following proved using modular arithmetic (where "=" means "congruent to")?

    1+2+...+(n-1)=0 mod n iff n is odd
    1^2+2^2+...+(n-1)^2=0 mod n iff n=+/-1 mod 6
    1^3+2^3+...+(n-1)^3=0 mod n iff n is not congruent to 2 mod 4

     1+2 +...+(n-1)=\frac{(n-1)n}{2}...can you see how the given condition on n makes this expression an integer multiple of n?
    Try to do the next ones in a similar way.

    1^1+2^2+...+(n-1)^2=\frac{n-1}{6}\,n\,(2n-1)

    1^3+2^3+...+(n-1)^3=\frac{(n-1)^2}{4}\,n^2

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    10
    Quote Originally Posted by tonio View Post
     1+2 +...+(n-1)=\frac{(n-1)n}{2}...can you see how the given condition on n makes this expression an integer multiple of n?
    Try to do the next ones in a similar way.

    1^1+2^2+...+(n-1)^2=\frac{n-1}{6}\,n\,(2n-1)

    1^3+2^3+...+(n-1)^3=\frac{(n-1)^2}{4}\,n^2

    Tonio
    For the sum of the first n cubes, if we let n=4k+i, where i={0, 1, 2, 3} we expect to NOT get an integer multiple of k in the case of 4k+2, which happens to be true when you work out the algebra. But, we would expect integer multiples of k in the other three cases. However, 4k+3 does not produce an integer multiple of k. What am I doing wrong?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by carabidus View Post
    For the sum of the first n cubes, if we let n=4k+i, where i={0, 1, 2, 3} we expect to NOT get an integer multiple of k in the case of 4k+2, which happens to be true when you work out the algebra. But, we would expect integer multiples of k in the other three cases. However, 4k+3 does not produce an integer multiple of k. What am I doing wrong?

    Thanks!

    n=4k+3 \Longrightarrow \left(\frac{n(n-1)}{2}\right)^2=\left(\frac{(4k+3)\cdot 2(2k+1)}{2}\right)^2= (2k+1)^2(4k+3)^2=(2k+1)^2\cdot n , an integer multiple of n, indeed.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2009
    Posts
    10
    Quote Originally Posted by tonio View Post
    n=4k+3 \Longrightarrow \left(\frac{n(n-1)}{2}\right)^2=\left(\frac{(4k+3)\cdot 2(2k+1)}{2}\right)^2= (2k+1)^2(4k+3)^2=(2k+1)^2\cdot n , an integer multiple of n, indeed.

    Tonio
    OOPS! I forgot to substitute on that next to last step. I can do the rest of these questions now. Thanks again, brother!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with summations.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 25th 2011, 11:37 AM
  2. Summations
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 6th 2010, 07:22 AM
  3. Replies: 1
    Last Post: November 7th 2010, 06:12 PM
  4. Summations
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 18th 2010, 07:53 PM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum