1
$\begingroup$

I need to prove by induction if ${n^5 - n}$ is divisible by 5 and I have no idea how I would do it.

I am trying to prove it for several hours now, I started with ${n^5 - n} \mod 5 = 0$ but then I realized that I have no idea how to use modulo for transformations.

The next thing I tried was $(5 + n)\frac{n^5 - n}5 = \frac{(n+1)^5 - n+1}5$ but it didn't get me anywhere.

How would you do it?

$\endgroup$
4

6 Answers 6

1
$\begingroup$

Let $\displaystyle f(n): n^5-n$ is divisible by $5$ holds true for $n=m$

$\displaystyle\implies 5\mid(m^5-m)$

Now, $\displaystyle f(m+1)-f(m)=(m+1)^5-(m+1)-(m^5-m)=\sum_{1\le r \le 4}\binom5 rm^r$ which is divisible by $5$

as each $\displaystyle\binom5r,1\le r\le4$ is divisible by $5$

Finally, establish the base case i.e., $n=1$

Generalization :

More generally prime $p$ divides $\displaystyle\binom pr$ (can you prove this?) for $1\le r\le p$ or more genrally $p\not\mid r$

So, we can prove $\displaystyle n^p-n$ will be divisible by $p$ (Fermat's Little Theorem)

$\endgroup$
7
  • $\begingroup$ Caution: indeed $\;p\;$ divides $\;\binom pr\;$ .... for $\;1<r<p\;$ (or also for $\;r>p\;$ if we define $\;r>p\implies \binom pr=0\;$ ) $\endgroup$
    – DonAntonio
    Feb 17, 2014 at 10:47
  • $\begingroup$ @DonAntonio, why "Caution"? $\endgroup$ Feb 17, 2014 at 16:30
  • $\begingroup$ Because what you wrote is not true for any $\;r\;$ , @lab $\endgroup$
    – DonAntonio
    Feb 17, 2014 at 18:42
  • $\begingroup$ @DonAntonio, thanks for pointing out, the restriction I wrote in the special case, forgot to include in the general one $\endgroup$ Feb 17, 2014 at 18:53
  • $\begingroup$ it still must be $\;r<p\;$ ... $\endgroup$
    – DonAntonio
    Feb 17, 2014 at 18:56
1
$\begingroup$

Let $p$ be any prime number. Consider the polynomial $f=X^p-X=X(X^{p-1}-1)\in \mathbb F_p[X].$ This polynomial is the zero function $\mathbb F_p\to\mathbb F_p$ if and only if $n^p-n$ is divisible by $p$ for all $n\in\mathbb Z$. Clearly $f(0)=0$ and $\mathbb F_p^\times$ is a group of order $p-1$ so for all $a\in\mathbb F_p^\times$ we have $a^{p-1}=1$. Now apply this to $p=5$.

$\endgroup$
1
$\begingroup$

Hint $\,\ {\rm mod}\ 5\!:\ n\equiv 0,\,\pm1,\,$ or $\, \pm2.\ $ $\ 0^5\!\equiv 0,\,\ (\pm1)^5\!\equiv \pm1,\,\ (\pm2)^5\!\equiv \pm32\equiv \pm2,\ $ so $\ n^5\!\equiv n.$

$\endgroup$
1
$\begingroup$

You can always try brute force in case you are stuck otherwise:

$$(n+1)^5=1+5 n+10 n^2+10 n^3+5 n^4+n^5$$ $$(n+1)^5-(n+1)=4 n+10 n^2+10 n^3+5 n^4+n^5$$ $$(n+1)^5-(n+1)-\big(n^5-n\big)=5 n+10 n^2+10 n^3+5 n^4=5(n+2n^2+2n^3+n^4)$$

$\endgroup$
1
$\begingroup$

Any natural number can be represented by $5k + q$, where $q = 0,1,2,3,4$. If we prove it for all mentioned $q$, then it will work with every natural.

$n^5 - n = n(n^4 - 1) = n(n - 1)(n + 1)(n^2 + 1)$.

By the nature of this expansion if we plug in $ n = 5k + q$, where $ q =0,1,4$, we will get something of the form $5k*f(k)$, which is divisible by $5$.

If $q = 2,3$, then $n(n-1)(n+1)$ will not return a multiple of $5$, so we look at $n^2 + 1$ :

$n^2 + 1 = (5k + q)^2 + 1 = 25k^2 + 10kq + q^2 + 1$

If $q = 2$, then $n^2 + 1 = 25k^2 + 20k + 5$

If $q = 3$, then $n^2 + 1 = 25k^2 + 20k + 10$

In both cases, the resulting coefficients are divisible by $5$. The polynomial is divisible by $5$, for all mentioned $q$. Thus the polynomial satisfies the required condition for all naturals.

$\endgroup$
-1
$\begingroup$

I would like to give you a more simple approach to this question: =>n^5-n is given to you. So, on taking n common n(n^4-1) is you got. so this expression has to be divisible by 5 the multiplication of both n and n^4-1 have to divisible by 5. And, Clearly for each number we have n^4-1 have to be divisible by 5. Now, calling the number Any number which has even in unit's place like 2,4,6,8 2^4=6 4^4=6 6^6=6 8^6=6 Any number which have even number in unit's place is leading to in 6 and subtracting 1 we got 5 so each expression is divided by 5 And, similarly for odd numbers 1^4=1 3^4=1 7^4=1 9^4=1 And, subtracting 1 from we got 0 so it is again divisible by 5. And, when we have 5 at unit's place n is divisible by 5. Sorry , for the poor presentable form, but I think this will work

$\endgroup$
2
  • $\begingroup$ Also please let me know why it is down-voted and why this approach wouldn't work. And, someone should comment also explaining to the other community member why their approach is wrong. $\endgroup$ Feb 16, 2014 at 17:15
  • $\begingroup$ I've no idea who downvoted your answer, but: (1) you didn't used LaTeX MathJax, making your post very hard to understand; (2) Some parts of the post are really obscure, to say the least, e.g. "calling the number Any number which has even in unit's place ...", "...place is leading to in 6...". At least you apologize at the end for the "poor presentable form", but I think that you should really enhance this if you want more people to read and understand your stuff. $\endgroup$
    – DonAntonio
    Feb 17, 2014 at 10:45

Not the answer you're looking for? Browse other questions tagged .