SOLUTION: How do u prove this?...Show that 3 divides n^3-n for all positive integers n. And does 4 divide n^4-n for all positive intgers n? AND i need to use proof by induction i think, i g

Algebra ->  Divisibility and Prime Numbers  -> Lessons -> SOLUTION: How do u prove this?...Show that 3 divides n^3-n for all positive integers n. And does 4 divide n^4-n for all positive intgers n? AND i need to use proof by induction i think, i g      Log On


   

Question 12319: How do u prove this?...Show that 3 divides n^3-n for all positive integers n. And does 4 divide n^4-n for all positive intgers n? AND i need to use proof by induction i think, i get the first part but then get stuck at the end...please help
Answer by khwang(438) About Me  (Show Source):
You can put this solution on YOUR website!
Show that 3 divides n^3-n for all positive integers n.
Proof: Claim: 3 isa divisor of +n%5E3-n+ for all integer n+%3E=+1
.....(**)
Basic: When n = 1 , +n%5E3-n+=+1%5E3-+1+=0
So, (**) is true when +n+=+1
Induction Hypothesis: When +n+=+k (**) is true.
Hence, there exists an integer q such that +k%5E3-k+=+3q+.
Consider +%28k%2B1%29%5E3-%28k%2B1%29+=+k%5E3+%2B+3%2Ak%5E2+%2B+3%2Ak+%2B+1+-+k+-1
= +k%5E3+-k+%2B+3%2Ak%5E2+%2B+3%2Ak++
= 3%2Aq+%2B3%2Ak%28k%2B1%29+
= +3%2A%28q%2B+k%5E2%2B+k%29+
This shows 3 is a divisor of +%28k%2B1%29%5E3-%28k%2B1%29+.
And so,the inductive proof is complete.

[Actually,+n%5E3-n is a product of three consecutive positive integers
for any positive integer n. Why ? ]
And does 4 divide n^4-n for all positive intgers n?
When n =2, n%5E4-n+=+16+-+2+=+14+
Hence 4 cannot divide n^4-n in general.
In fact, n%5E4-n+=+n%2A%28n%5E3+-1%29+=n%2A%28n-1%29%28n%5E2%2Bn%2B1%29+
Clearly, 2 is a divisor of n%2A%28n-1%29
We only can claim 2 divides n%5E4-n+ for all positive n.
Kenny