Can I used polynomial congruence for prove 3 divide $n^3-n$?

Question

I'm not sure this method can work to prove 3|$n^3-n$?

by let we have polynomial congruence

$n^3-n\equiv 0(mod3)$

then if all residue class mod 3 are the roots of congruence 3|$n^3-n$

the residue for mod 3 are 0,1,2

then I plug each of them in congruence

start by 0

$0-0\equiv 0(mod3)$ congruence

then 1

$1-1\equiv 0(mod3)$ congruence

and 2

$8-2\equiv 0(mod3)$ congruence

then concluded 3|$n^3-n$

Does it work ?

Answer 1

You can justify that the problem is reduced to remainders modulo $3$ like this:

Let $n=3q+r$ with $r\in\{0,1,2\}$ then

$n^3-n=(3q+r)^3-(3q+r)=27q^3+27q^2r+9qr^2+r^3-3q-r\equiv r^3-r\pmod 3$

Then your method of evaluating the value for each $r$ is fine, and you get the conclusion it works for all integers.

Answer 2

$n^3-n$ factors as $(n-1)n(n+1)$. For any integer $n$ it is easy to prove that one of the factors must be divisible by $3,$ so $n^3-n\equiv0\pmod3.$

Answer 3

Yes, it works. (You should state that it is $n$ you are taking the equivalence classes of-- you never actually stated that). If $n \equiv 0, 1 ,2 \mod 3$ then $n^3 -n \equiv 0-0, 1-1, 8-2 \mod 3$ respectively.

You can make it a tad more wieldy you could say $n\equiv -1, 0, 1\mod 3$ to get $-1+1, 0-0, 1-1 \mod 3$ respectively.

And that is fine. It does do everything a proof needs to do: it demonstrates irrefutably that the statement is true.

......

But 1) the text probably want a more intuitive, less brute force method and 2) for a more complex situation of a possibly high modulus such a proof may not be feasible or practical.

What they are getting at is to factor $n^3-n = n(n-1)(n+1)$. Those, $n, n+1, n-1$ are three consecutive integers so one of them must be divisible by $3$.

.......

Consider instead $n^7-14n^5 + 49n^3-36n$ and proving it is divisible by $5040$ is going to be impractical be brute force ($5040$ cases to check!) (Although a computer doing it would be an acceptable, albeit inelegant proof).

But factoring it as $(n-3)(n-2)(n-1)n(n+1)(n+2)(n+3)$ and noting it is a product seven consective integers so one of the terms is divisible by $7$, and least one is by $5$. Two are by $3$ and three are by $2$ with at least one by $4$. So $7*5*3^2*2*2*4=5040$ divides it.