# Prove $(n^5-n)$ is divisible by 5 by induction.

So I started with a base case $n = 1$. This yields $5|0$, which is true since zero is divisible by any non zero number. I let $n = k >= 1$ and let $5|A = (k^5-k)$. Now I want to show $5|B = [(k+1)^5-(k+1)]$ is true....

After that I get lost.

I was given a supplement that provides a similar example, but that confuses me as well.

Here it is if anyone wants to take a look at it:

Prove that for all n elements of N, $27|(10n + 18n - 1)$.

Proof: We use the method of mathematical induction. For $n = 1$, $10^1+18*1-1 = 27$. Since $27|27$, the statement is correct in this case.

Let $n = k = 1$ and let $27|A = 10k + 18k - 1$.

We wish to show that $27|B = 10k+1 + 18(k + 1) - 1 = 10k+1 + 18k + 17$.

Consider $C = B - 10A$ ***I don't understand why A is multiplied by 10. $= (10k+1 + 18k + 17) - (10k+1 + 180k - 10)$

$= -162k + 27 = 27(-6k + 1)$.

Then $27|C$, and $B = 10A+C$. Since $27|A$ (inductive hypothesis) and $27|C$, then $B$ is the sum of two addends each divisible by $27$. By Theorem 1 (iii), $27|B$, and the proof is complete.

-
Hint: can you write $(k+1)^5-(k+1)$ in terms of $k^5-k$? Obviously there will be something left over, but can you prove that is also divisible by 5 another way? – Michael Grant Apr 4 '13 at 1:15
What if I factor out a k? I believe that would give me $k^5 - 5$. – blutuu Apr 4 '13 at 1:18
But you don't know anything about $k^5-5$. Oh well, it looks like someone answered for you! Which is fine, but I was hoping with a little hint you could get it! :-) – Michael Grant Apr 4 '13 at 1:19
I guess, it wants to go to the exponent, $27\,|\,10^n+18n-1$, and then $10^{k+1}+18k+17$... – Berci Apr 4 '13 at 1:21

Your induction hypothesis is that $5\mid k^5-k$, which means that $k^5-k=5n$ for some integer $n$. Now
\begin{align*} (k+1)^5-(k+1)&=\left(k^5+5k^4+10k^3+10k^2+5k+1\right)-(k+1)\\ &=k^5+5k^4+10k^3+10k^2+5k-k\\ &=(k^5-k)+5k^4+10k^3+10k^2+5k \end{align*}
can you see why that must be a multiple of $5$?
I understand the base case where it states $k^5 - k = 5n$, which holds true. Expanding $(k+1)^5$ shows that it also is a multiple of 5 which is visible by factoring ($k^5 - 5)--a multiple of 5. Am I reading that correctly? – blutuu Apr 4 '13 at 1:52 @blutuu:$k^5-k=5n$isn’t the base case; the base case is either$5\mid 0^5-0$or$5\mid 1^5-1$, depending on just how the theorem was stated.$5\mid k^5-k$is the induction hypothesis. It’s not that$(k+1)^5$is a multiple of$5$; in general it isn’t. What the calculation shows is that$(k+1)^5-(k+1)$is a multiple of$5$if$k^5-k$is, which is exactly what we need to show for the induction step. – Brian M. Scott Apr 4 '13 at 1:55 That last sentence clears up my confusion. Thanks. – blutuu Apr 4 '13 at 2:25 @blutuu: Oh, good. You’re welcome. – Brian M. Scott Apr 4 '13 at 2:27 Hint$\ \ n^5\!-\!n = n(n^2\!-\!1)(n^2\!-\!4\! +\! 5) = (n\!-\!2)(n\!-\!1)n(n\!+\!1)(n\!+\!2)+ 5n(n^2\!-\!1)$Thus it suffices to show that$\,5\,$divides a product of$\,5\,$consecutive integers. In fact, any sequence of$\,n\,$consecutive naturals has an element divisible by$\,n\,$. This has a simple proof by induction: shifting such a sequence by one does not change its set of remainders mod$\,n,\,$since it effectively replaces the old least element$\:\color{#C00}a\:$by the new greatest element$\:\color{#C00}{a+n}$$$\begin{array}{}& \color{#C00}a, &\!\!\!\! a+1, &\!\!\!\! a+2, &\!\!\!\! \cdots, &\!\!\!\! a+n-1 & \\ \to & &\!\!\!\! a+1,&\!\!\!\! a+2, &\!\!\!\! \cdots, &\!\!\!\! a+n-1, &\!\!\!\! \color{#C00}{a+n} \end{array}\qquad$$ Since$\: \color{#C00}{a\,\equiv\, a\!+\!n}\pmod n,\:$the shift does not change the remainders in the sequence. Thus the remainders are the same as the base case$\ 0,1,2,\ldots,n-1\ =\: $all$ $possible remainders mod$\,n.\,$Therefore the sequence has an element with remainder$\,0,\,$i.e. an element divisible by$\,n.$- Also note that all the binomial coefficients$C(p, k) = \frac{p!}{k!(p-k)!}$when$p$is a prime are divisible by$p$except for$k=0$and$k=p$(since$p$is in the numerator but not in the denominator). This is enough to show by induction that$n^p-n$is divisible by$p$for all positive integers$n$: True for$n=1$and, for the induction,$\begin{align} ((n+1)^p-(n+1))-(n^p-n) &=(n+1)^p-n^p-1\\ &= (n^p+(\text{terms divisible by p})+1)-n^p-1\\ &= (\text{terms divisible by p}) \end{align}\$ .