Question

Prove:
3 divides (n^(3) - n) n is an element of N

Answer 1

you can use Fermat's Little Theorem
n^(p-1) = 1 (mod p)
so

n^p = a (mod p)

n^3 = n (mod 3)
so 3|n^3 - n

or doing it the other way
factor the n^3 - n = n(n^2 - 1) = n(n+1)(n-1)

if 3 divides n^3 - n then it divides n(n+1)(n-1)
so this means at least one of these n, n+1, n-1 is divisible by 3 and you just need to check it at 1,2,3
when n = 1 you get 1, 2, 0 = 0 divisible by 3
n= 2 you get 2, 3, 1 = 3 divisble by 3
n = 3 you get 3, 4, 2 = 3 divislbe by 3

and the other method i would use is induction
base case: n= 1 so 1^3 - 1 = 0 true
the assume arbitrary k where k^3 - k = 3x where x in Z
and prove for k+1

(k+1)^3 - (k+1) = 3x
(k+1)((k+1)^2 - 1)
(k+1)(k^2 + 2k + 1 - 1)
(k+1)(k^2 + 2k) = 3x
k^3 + 2k^2 + k^2 + 2k = k^3 + 3k^2 + 2k = k^3 - k + 3k^2 + 3k = 3x
by inductive hypothesis
3z + 3k^2 + 3k = 3x where z is an integer
so 3(z + k^2 + k) = 3x
so 3 divides this equation so this holds for k+1 which holds for n

Answer 2

i might be doing the 2nd method wrong so i would recommend induction instead

Answer 3

Can you show me induction with this problem?

Answer 4

i showed it as the 3rd method
you want to do
base case: n= 1 so 1^3 - 1 = 0 true the assume arbitrary k where \[3 | k^3 - k\] and prove for k+1

\[3|(k+1)^3 - (k+1)\]

Answer 5

divisor also means
\[(k+1)^3 - (k+1) = 3x\] where \[x \in \mathbb{Z}\]

so first factor out a k+1
\[(k+1)((k+1)^2 - 1) = 3x\]

Answer 6

So what step did you think was wrong. ^

Answer 7

then multiple the inside out
\[(k+1)(k^2 + 2k + 1 - 1) = (k+1)(k^2 + 2k) = 3x\]
distribute again
\[k^3 + 2k^2 + k^2 + 2k = k^3 + 3k^2 + 2k = 3x\]

Answer 8

The induction is did in the first post is fine its just the 2nd method that i think it was wrong

im showing you step by step on how to do this with induction, what part are you confused about?

Answer 9

I am confused about what you said is wrong. I do not want to learn it incorrect.

Answer 10

anyways you now have
\[k^3 + 3k^2 + 2k = 3x\]
add and subtract k on the LHS
\[k^3 + 3k^2 + 2k + k - k= 3x\]
\[(k^3 - k)+ 3k^2 + 3k= 3x\]
the by inductive hypothesis
3z + 3k^2 + 3k = 3x where z is an integer
factor out a 3
3(z+k^2 + k) = 3x
so this holds for k+1 which implies it holds for n

Answer 11

i showed you all the correct steps for the induction problem i hope you are reading what i am writing/understanding

just look at my 3rd post and start from there

Answer 12

I understand.

Answer 13

alright then glad to help