# Thread: Congruence Proofs: Summations

1. ## 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

2. Originally Posted by carabidus
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

$\displaystyle 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.

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

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

Tonio

3. Originally Posted by tonio
$\displaystyle 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.

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

$\displaystyle 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!

4. Originally Posted by carabidus
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!

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

Tonio

5. Originally Posted by tonio
$\displaystyle n=4k+3 \Longrightarrow \left(\frac{n(n-1)}{2}\right)^2=\left(\frac{(4k+3)\cdot 2(2k+1)}{2}\right)^2=$ $\displaystyle (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!