Proving x^n - x is Divisible by n: A Guide for Induction Method

[grizz45]

im stuck on this proof can anyone help?

Is it true that for all natural numbers n, for each natural number x, x^n − x is
divisible by n? If so, prove it; if not, explain why not.


so far i have gotten:

make x=1, ((1)^n) -1 = 0, therefore x=1 is divisible by n

assume true for x=k, ie: (k^n) - k is divisible by n

make x=k+1; ((k+1)^n)-(k+1)...and that's it!

 

[Mark44]

Before attempting to prove it, you should first do some work to see if it's actually true. Test the statement with a number of values of n.

If you believe that it's true, you should be doing your induction on n, not x. Your base case is for n = 1. Can you show that x^1 - x is divisible by 1? If that's too obvious, see if if holds for n = 2. IOW, can you show that x^2 - x is divisible by 2?

x^2 - x = x(x - 1)
If x is even, you're done, since an even number times an odd number is even.
If x is odd, then x - 1 is even, and you're done.

Now, assume that x^n - x is divisible by n, which means that x^n - x = a*n for some integer a.
The final step is to show that x^(n + 1) - x is divisible by (n + 1), using the induction hypothesis that x^n - x is divisible by n.

 

[Architeuthis Dux]

First of all, great job on starting the proof! You're on the right track. To finish the proof, you can use mathematical induction. This method involves three steps: base case, inductive hypothesis, and inductive step.

Base case: As you have already shown, when x=1, x^n - x is divisible by n.

Inductive hypothesis: Assume that for some natural number k, x^k - x is divisible by n.

Inductive step: We want to show that for x=k+1, x^(k+1) - x is also divisible by n. Let's expand this expression using the binomial theorem:

x^(k+1) = (k+1)^n = k^n + nk^(n-1) + ... + nC2*k^2 + nC1*k + nC0

Subtracting x = k from both sides, we get:

x^(k+1) - x = (k^n + nk^(n-1) + ... + nC2*k^2 + nC1*k + nC0) - k

= (k^n - k) + nk^(n-1) + ... + nC2*k^2 + nC1*k + nC0

Since we assumed that x^k - x is divisible by n, we can replace it with a multiple of n:

x^(k+1) - x = mn + nk^(n-1) + ... + nC2*k^2 + nC1*k + nC0

= n(m + k^(n-1) + ... + nC2*k + nC1) + nC0

Since n is a common factor in all terms, x^(k+1) - x is also divisible by n. This completes the inductive step.

Therefore, by the principle of mathematical induction, x^n - x is divisible by n for all natural numbers x.