3
$\begingroup$

How do you prove that $n^5 \equiv n\pmod {10}$ Hint given was- Fermat little theorem. Kindly help me out. This is applicable to all positive integers $n$

$\endgroup$
  • 3
    $\begingroup$ I know its not what you are looking for, but you could just check 0,1,2,3,4,5,6,7,8,9 each to the fifth power and see if they are congruent each $\endgroup$ – Asimov Jun 9 '14 at 2:58
  • $\begingroup$ Note that this is not a duplicate of the prior listed question since that question asked for a proof without modular arithmetic, whereas this question uses modular arithmetic (and is tagged modular arithmetic). $\endgroup$ – Gone Jun 9 '14 at 18:16
  • $\begingroup$ Anyway, leaving at least a link to the other question might be useful: math.stackexchange.com/questions/404157/n5-n-is-divisible-by-10 $\endgroup$ – Martin Sleziak Jun 9 '14 at 19:07
8
$\begingroup$

Here's a direct proof: note that $$n^5 - n = n(n^4-1) = n(n-1)(n+1)(n^2+1)$$

You need to prove that this number is divisible by $2$ and $5$.

  • For divisibility by $2$, note that either $n$ or $n+1$ must be even.

  • For divisibility by $5$, you should prove that if neither $n$ nor $n \pm 1$ is divisible by $5$ (i.e. if $n \equiv 2\ \text{or}\ 3 \bmod 5$) then $n^2+1$ is divisible by $5$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Well, then that's done... ain't it? @ clive newstead $\endgroup$ – Krishnaar Jun 9 '14 at 3:03
5
$\begingroup$

Hint: In order to use Fermat's Little Theorem, you need the modulus to be prime which $10$ is not. However, $10 = 2\times 5$. Use Fermat's Little Theorem for each prime and see if you can combine these results to arrive at your claim.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

By Fermat's Little Theorem, $n^5 \equiv n \pmod 5$

Also $n \equiv 0 \ or \ 1 \pmod 2 \implies n^5 \equiv n \pmod 2$

Chinese Remainder Theorem guarantees the presence of a solution $\pmod {10}$ as $(2,5) = 1$

From the second congruence, $n^5 = 2k + n$

Substitute into the first congruence, $2k+n \equiv n \pmod 5 \implies 2k \equiv 0 \pmod 5 \implies k \equiv 0 \pmod 5$

So $k = 5m$

Substitute that into second congruence, $n^5 = 2(5m) + n = 10m +n$

Therefore, $n^5 \equiv n \pmod {10}$ $\rm{(QED)}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Perhaps this is the best solution. Sorry, but I quite didn't get the last two/three steps from taking the congruence as 2k+n. can you further explain? $\endgroup$ – Krishnaar Jun 12 '14 at 16:53
  • $\begingroup$ You get $n^5\equiv n\pmod 2$, right? This is because the only possible values of $n\pmod 2$ are $0$ or $1$. The fifth powers of those residues simply return to $0$ or $1$ respectively. Now from $n^5\equiv n\pmod 2$ you can conclude that $n^5-n=2k$ and hence $n^5 = 2k + n$. I sub that into first congruence to get $2k+n=n\pmod5$. I subtract $n$ from both sides giving $2k=0\pmod 5$ since $(2,5)=1$, it has to be that $5 \mid k$. So $k=5m$. I put that back into $n^5=2k+n$ and the rest is just algebra. From $n^5= 10m+n$, it should be clear that the $10m$ vanishes $\pmod{10}$, leaving the result. $\endgroup$ – Deepak Jun 13 '14 at 1:38
  • $\begingroup$ Tell you the truth, it is possible to solve this more simply but less elegantly by considering the few cases $\pmod{10}$. $n \equiv 0,\pm1,\pm2,\pm3,\pm4,\pm5 \pmod{10}$. When you take the fifth power, the odd power does not change the sign of the $\pm$. Obviously $0^5\equiv 0 \pmod{10}$, and the same applies to $1$. All that remains is for you to test $2^5,3^5,4^5,5^5 \pmod{10}$ to verify that they return to $2,3,4,5$ respectively (just look at the last digit) and you've proved the proposition. This method is sound and elementary, but doesn't feel as satisfying for some reason.:) $\endgroup$ – Deepak Jun 13 '14 at 1:44
  • $\begingroup$ Thank you very much. It was cool :) $\endgroup$ – Krishnaar Jun 13 '14 at 12:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.