Divisibility Proof for Odd Integers

Date: 02/13/2002 at 02:16:47
From: Mike Smith
Subject: Divisibility proof for odd integers

I really like your site. I'm an applied math major and I enjoy 
reading your college and beyond section often. That said, here's my 
question:

How can I prove that for all odd integers N, N^3 - N is divisible by 
8? I know it's divisible by 4, I've gotten that far (using a 2k+1 
sub. for N^3 - N and pulling out 4 as a factor) already. Where next? 
I want to say that 

>> if a number is divisible by 4 and it is divisible by 2, then it is 
divisible by 8.

I know that this is incorrect. 28, voila.

I'm only a beginner in the proofwriting realm, so any direction would 
be helpful.  I'm sure it's something obvious that I'm overlooking...

Thank you,
Mike

Date: 02/13/2002 at 02:48:02
From: Doctor Schwa
Subject: Re: Divisibility proof for odd integers

Hi Mike,

Sounds like you're off to a great start on this problem!

With your approach, N = 2k+1, you get
(2k+1)^3 - (2k+1) = 8k^3 + 12k^2 + 4k, right?

Now that is 4(2k^3 + 3k^2 + k), or, factoring, you have 
4k(2k+1)(k+1) ...

What I notice there is that you have both k and k+1 as factors, one of 
which must be even ... and thus the problem is solved.

I took a slightly different approach from the beginning, with a little
less messy algebra but slightly more subtle reasoning necessary:

n^3 - n = n(n+1)(n-1).

Now if n is odd, n+1 and n-1 are both even, and of any two consecutive 
even numbers like that, what can you conclude?

Enjoy,

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/