Prove for every positive integer n: 3 divides evenly into n^3 - n?

Question

If someone could help me with this one, I'm almost entirely lost as to what methods will work for this....

Prove for every positive integer n: 3 divides evenly into n^3 - n

I.e. 3 will divide evenly into n^3 - n with no remainder left.

My prof seemed to recommend induction, but I don't see how to do that here...and then I tried to do it by cases, but the first case i tried (when n is odd) won't seem to do me any good (it reduces to 8k^2(k+2)+2 ....how can i prove that's divisible by 3??)

Thanks in any case, I need the help!!

Answer 1

Factor n^3 - n first.
n^3 - n = n(n^2 - 1) = n(n+1)(n-1) = (n-1)(n)(n+1)

So (n^3 - n) is the product of three consecutive integers.

Since given any three consecutive integers, one of them has to be a multiple of three.

Let (n-1) be the multiple of 3. So 3 divides (n-1).
This implies 3 also divides (n-1)(n)(n+1)

Similarly
Let (n) be the multiple of 3. So 3 divides (n).
This implies 3 also divides (n-1)(n)(n+1)

Similarly
Let (n+1) be the multiple of 3. So 3 divides (n+1).
This implies 3 also divides (n-1)(n)(n+1)

So its true in all three cases.

You don't have to use induction unless you want to.

Answer 2

Although you have not seen it, the idea that leads to the solution of this problem is quite simple and easy to comprehend.

First try to factorize the given expression;
n^3 - n = (n-1)(n)(n+1)

Now let us exmine the 3 factors;
(n-1), n and (n+1) are three consecutive intergers. Therefore 3 will divide evenly into any one of them. For instnce, take the three numbers 28, 29 and 30. As you see 3 will divide evenly into 30. Once again take 1001, 1002 and 1003 and you will see that 3 will divide evenly into 1002.

If one of the factor of an expression can be devided by 3 with no remainder, 3 will divide evenly into the expression.

If you want to know more about these things try to get hold of book on number theory.

Have a nice day!

Answer 3

Assume it works for n = k, then for n=k+1, the expression is

(k+1)^3 - (k+1) =
(k+1)[(k+1)^2 - 1] =
(k+1)[ k^2 + 2k + 1 - 1 ] =
(k+1)[ k^2 + 2k ] =
k^3 + k^2 + 2k^2 + 2k =
k^3 + 3k^2 + 2k =
3k^2 + k^3 + 2k =
3k^2 + (k^3 - k) + 3k

We already assumed that k^3 - k is a multiple of 3. And obviously, 3k^2 and 3k are both multiples of 3. That means the sum of these three terms is a multiple of 3, because you can factor a 3 out.

This proves that if it works for n=k, it works for n=k+1. Finally, we notice that if n=1, we get 1^3 - 1 = 0 which is divisible by 3. This finishes the proof.

Another way to prove this is to think of all positive integers as being in the form of 3m + r, where m is an integer and r is 0, 1, or -1. Then n^3 - n is
n(n^2 - 1) =
(3m + r)((3m+r)^2 - 1) =
(3m + r)(9m^2 + 6mr + r^2 - 1) =
(27m^3 + 18m^2 r + 3mr^2 - 3m) + (9m^2 r + 6mr^2 + r^3 - r)=
27m^3 + 27m^2 r + 9mr^2 - 3m + r^3 - r
3(9m^3 + 9m^2 r + 3mr^2 - m) + r(r^2 - 1)

Whether r = 0, 1, or -1, the term on the right end will be 0. This leaves a multiple of 3 on the left.

Answer 4

For the best answers, search on this site https://shorturl.im/avcc4

7!=5040, 3^7=2187. So n!>3^n for n=7. Assume for some n, n! > 3^n. For n+1, (n+1)! - 3^(n+1) = (n+1)*n! - 3* 3^n > 3*n! - 3*3^n = (n! - 3^n) 3 > 0 from induction hypothesis. Therefore (n+1)! > 3^(n+1) is also true. QED. -------------------------- When n=1, 7^1 - 2^1 = 5 is divisible by 5. Assume for some n, 7^n - 2^n is divisible by 5. For n+1, 7^(n+1) - 2^(n+1) = 7*7^n - 2*2^n = 5*7^n + 2*7^n - 2*2^n = 5*7^n + 2*(7^n - 2*2^n) The first term 5*7^n is divisible by 5, the second is also divisible by 5 from hypothesis. Therefore, 7^(n+1) - 2^(n+1) is divisible by 5. QED

Answer 5

You almost had the right idea, except you needed to look at 3 cases, not 2.

That said, there are three good answers up already, so I'll stop here.