Discrete math - proof of divisibility question

[automan13]

1. For any integer n, prove that 3 divides n^3 -n

The Attempt at a Solution

I'm stuck. I understand that means that n^3 -n mod 3 =0.
or I can n^3 -n can be expressed as 3x.
But I don't know how to prove it.
Where do i go from here. Thanks

 

[spamiam]

Welcome to the forum, automan!

Um, this "theorem" looks false to me. For instance, 2³ -1 = 7 and 5³ -1 = 124 neither of which is divisible by 3...

Anyway, in general statements involving the positive integers can often be proved using induction.

 

[automan13]

Sorry, had a typo. 3 divides n^3 -n .
Also i can't use induction. All we've learned so far is proof by cases, direct proof, contrapositive and contradiction.

 

[spamiam]

Ah, much better!

The first thing I would do is factor your expression. Next, a proof by cases would work using 3 cases, one for each of the 3 equivalence classes of \mathbb{Z}/3\mathbb{Z}. So what are the 3 things an integer can be equivalent to mod 3?

Actually, a shorter proof can just include 2 cases. What are the 2 things n² can be congruent to mod 3?

 

[TROGLIO]

n^3 - n
nx(n^2 -1)
n x (n-1) x (n +1) let's say this = A


now consider (n+1)C3
ie the number of ways of choosing 3 objects from n+1
it wil always b an integer (n+1)C3 = integer
i can't chose half an object
(n+1)C3 = (n+1)x(n)x(n-1)/3
integer = A/3
hence A is divisible by 3

 

[HallsofIvy]

Thats more complicated than necessary. n-1, n, and n+1 are three consecutive integers. One of them must be a multiple of three.

 

[automan13]

TROGLIO thanks big time. I should have thought of factoring it. It becomes obvious from there.
Thanks Again

 

[TROGLIO]

Thats more complicated than necessary. n-1, n, and n+1 are three consecutive integers. One of them must be a multiple of three.

nice 1 pure genius
i need some help with modulo theory
i dnt know a thing about it
any free e books or any material would do