Modulus problem

dobedobedo

I would like to know how to prove that the number n^3 + 2n is divisible by 3 for all integers n. I know that I am supposed to examine the possible remainders after division with 3. The possibilities are:

n= 0,1,2 (mod 3)

Could somebody please help me? How can the expression of n^3 + 2n possibly become a number composed by at least one factor 3?

Thank you by forehand,
dobedobedo

rollcast

Do you understand the Induction Hypothesis?

dobedobedo

No, I do not have much experience with modulus calculation and I haven't heard of that hypothesis. I do understand the basic theorems:

If:
α= β (mod C)
and
a = b (mod C)

Then
α*a = β*b (mod C)
and
α + a = β + b (mod C) [1]

I've made some tables showing the mod 3 values for numbers n^3 and 2n:

[2n] 0 2 4 6 8 10 12 14 16
[mod 3] 0 2 1 0 2 1 0 2 1

[n^3] 0 1^3 2^3 3^3 4^3 5^3 6^3 7^3 8^3
[mod 3] 0 1 2 0 1 2 0 1 2

According to [1], 2n + n^3 should be divisible by 3 (if you add the numbers of the rows corresponding to mod 3, you will get always 3 or 0, so the number is divisible by 3 SEE BELOW), if the patterns above don't stop repeating themselves.
[2n+n^3]
[mod 3] 0 3 3 0 3 3 0 3 3

The only problem I see, is that I am unable to prove that this pattern, of numbers congruent to 2n and n^3, repeats in all eternity, making the sum of [2n] and [n^3] equal to 3 or 0.
What is the induction hypothesis btw?

rollcast

I'd use the induction hypothesis to prove it.

Basically the induction hypothesis shows that if something works for n then it will work for n + 1, which then shows it will work for all values of n.

http://en.wikipedia.org/wiki/Mathematical_induction

That should explain it in more detail.

First of all you need a basis, to do this show that your hypothesis (that its divisible by 3 for all values of n) works for a small value of n - you can use either n = 0 or n = 1.

Then you substitute in n+1 for n in your first expression.

So in full your proof should look a bit like:

For any natural number n, n³ + 2n is divisible by 3.

Proof:

Basis: If n = 0, n³ + 2n = 0³ + 2×0 = 0.
0 mod 3 = 0, therefore it is divisible by 3.


Induction: Assume that for an arbitrary natural number n, n3 + 2n is divisible by 3.

Induction Hypothesis: To prove this for n+1, first try to express ( n + 1 )³ + 2( n + 1 ) in terms of n³ + 2n and use the induction hypothesis.

( n + 1 )³ + 2( n + 1 ) = ( n³ + 3n² + 3n + 1 ) + ( 2n + 2 )
= ( n³ + 2n ) + ( 3n² + 3n + 3 )
= ( n³ + 2n ) + 3( n² + n + 1 )

Therefore n³ + 2n is divisible by 3 by the induction hypothesis.

I'm not great with proofs so prehaps someone else could just check that.

dobedobedo

I am a little confused. The term 3(n^3 + 1) is certainly divisible by 3 - but what about the other term (n^3 + 2n) ? Aren't we back at the same situation?

rollcast

With the inductive hypothesis, we assumed that n³+2n was divisible by 3 for n, and now you're proving the same for n + 1.

It's like knocking down a line of dominoes, if we can prove that the first domino falls over (basis) and each domino knocks over the next (inductive step), then that means that all of the dominoes in the line get knocked down eventually.

You know that (n³+2n)+3(n²+n+1) is divisible by 3 because n³+2n is (because of the inductive hypothesis) and 3(n²+n+1) is (because it's 3 times an integer). So, their sum is as well.

dobedobedo

Ok, thank you very much for your suggestion, but on the wikipedia article it says that induction works for positive integers. If I would like to extend my reasoning to include negative integers as well - what would be an effective way of proving that n^3 + 2n is divisible by 3 for all n?

HallsofIvy

Well, go back to your orginal idea of looking at it "modulo 3".

All integers are equivalent to 0, 1, or 2. If n= 0, [itex]n^3+ 2n= 0^3+ 2(0)= 0[/itex]. If n= 1 [itex]n^3+ 2n= 1^3+ 2(1)[/itex] mod 3. if n= 2,. [itex]n^3+ 2n= 2^3+ 2(2)[/itex] modulo 3. What do those tell you?

Another, related, way- every integer, n, is equal to one of 3m, 3m+1, or 3m+ 2. Calculate [itex]n^3+ 3n[/itex] for each of those.

dobedobedo

That helped, now I am very satisfied. :) Thank you very much, both of you.