# Simple proof

1. Sep 28, 2013

### phospho

is n = m^3 - m for some integer m, then n is a multiple of 6

how do I proof this?

I tried to do it by condradiction by assuming n is not a multiple of 6, i.e. when n is divided it is in the form of n = 1+k, or n = 2+k or n = 3+k or n = 4+k or n=5+k for some integer k

however I wasn't able to get anywhere, any help?

2. Sep 28, 2013

### Office_Shredder

Staff Emeritus
By 1+k or 2+k or 3+k I think you mean 1+6k or 2+6k etc.

You might want to try doing this with m instead of n.

3. Sep 28, 2013

### phospho

I don't get it, why?

4. Sep 28, 2013

### HallsofIvy

Staff Emeritus
Factor m^3- m. What do you get?

5. Sep 28, 2013

### phospho

m(m^2-1) = m(m-1)(m+1)

6. Sep 28, 2013

### Office_Shredder

Staff Emeritus
Did you try doing it? What did you get?

Factoring is actually a much cleaner way of doing this than my suggestion... can you explain why (m-1)(m)(m+1) is divisible by 6?

7. Sep 28, 2013

### phospho

I don't understand what your suggestion is trying to make me do, and I don't see why that's divisible by 6 (though I tried a few examples).

8. Sep 28, 2013

### phospho

ok I understand why that divides by 6

but I think the book wants me to use contradiction - how would I do that?

9. Sep 28, 2013

### HallsofIvy

Staff Emeritus
Okay, you understand that $n= m^3- m= (m-1)(m)(m+1)$, the product of three consecutive numbers. So at least one of those (in fact, one of any two consecutive numbers) is even and one of them is a multiple of 3. That proves that n is divisible by 6 and I don't see why you would want any proof.

I suppose you could say "Suppose n is not divisible by 6. Then either it is not divisible by 2 or it is not divisible by 3.

Since 2 is a prime number, if n is not divisible by 2, no factor of n is not divisible by 2. In particular, m- 1 is not divisible by 2. In that case m- 1 is odd: m-1= 2k+ 1 for some integer k. Then m= m-1+ 1= 2k+ 1+ 1= 2k+ 2= 2(k+ 1) is divisible by 2, a contradiction.

Since 3 is a prime number, if n is not divisible by 3, no factor of n is divisible by 3. In particular, m-1 is not divisible by 3 which means m-1= 3k-1 or m-1= 3k+1 for some integer k. If m-1= 3k- 1 then m= m-1+1= 3k-1+ 1= 3k is divisible by 3, a contradiction. If m-1= 3k+ 1, then m+1= m-1+ 2= 3k+1+ 2= 3k+ 3= 3(k+1) is divisible by 3, a contradiction."

But that is much more complicated than a direct proof so I cannot imagine why you would not use the simpler direct proof.