Why is $a^{5} \equiv a\pmod 5$ for any positive integer?

Why is $a^{5} \equiv a\pmod 5$ for any positive integer?

I feel like it should be obvious, but I just can't see it. Any help appreciated.

Edit: without Fermat's theorem.

• Isn't this a direct application of Fermat's Little Theorem? Mar 21, 2015 at 1:23
• Fermat's little theorem: en.wikipedia.org/wiki/Fermat%27s_little_theorem Mar 21, 2015 at 1:24
• @Deepak Which is usually a hint that the OP doesn't know the theorem. Mar 21, 2015 at 1:25
• possible duplicate of Purpose of Fermat's Little Theorem Mar 21, 2015 at 1:26
• @Deepak: Thomas got it right, I'd never heard of the theorem before.
– Bob
Mar 21, 2015 at 1:28

OK, without using Fermat's Little Theorem (a far more general and elegant result), here's another easy workaround.

Any integer $a$ can be exactly one of $0, 1, 2, -2, -1 \pmod 5$.

Take the fifth powers of each of those and see them reduce back to the original residue in each case.

One way to prove this is to prove it by induction. If $n^5\equiv n\pmod 5$ show that $(n+1)^5\equiv n+1\pmod 5$.

Note that $$(n+1)^5=n^5+5n^4+10n^3+10n^2+5n+1\equiv n^5+1\equiv n+1\pmod5$$

The general theorem people have mentioned in comments, Fermat's Little Theorem, states that if $p$ is prime and $a$ is any number: $a^p\equiv a\pmod p$.

• Huh. I didn't know you can prove the theorem like that (by induction). That's neat. Also pretty obvious in hindsight. But still neat. Mar 21, 2015 at 1:34
• Only works for positive $n$. Can prove for negative in one step, though, from the positives, since $5$ is odd. :) Mar 21, 2015 at 1:35
• This is nice, you just have to know that $\binom{p}{k}$ is divisible by $p$ for all $0<k<p$. Mar 21, 2015 at 1:41
• I was trying to keep it absolutely minimal to prove just for the case $5$, but yes, the general Fermat can be proved that way, @TravisJ. My favorite way to prove FLT is combinatorial - counting the number of ways of painting $p$ beads in a circle with $n$ colors. There are $n$ solid necklaces, and then the rest of the colorings can be grouped in sets of $p$ by rotation. Mar 21, 2015 at 1:44
• @Bob Note that all multiples of $5$ immediately reduce to $0$ modulo $5$. Mar 21, 2015 at 2:17

Consider $$a(a-1)(a-2)(a-3)(a-4)=a(a^4-10a^3+35a^2-50a+24).$$ Taken mod $5$ this becomes $$a(a^4-1).$$and so $a^5-a \equiv 0 \mod 5$, or $a^5 \equiv a \mod 5$ as required.

Note $\ a(a^4\!-1\!)\, =\, a(a^2-1)\overbrace{(a^2+1)}^{\Large \color{#0a0}{a^2-4}\,+\,\color{#c00}5} = \!\!\!\underbrace{a(a^2-1)(\color{#0a0}{a^2-4})}_{\large\color{blue}{ (a-2)(a-1)a(a+1)(a+2)}}\!\!\!\! + \color{#c00}5\,a(a^2-1)$

$\color{#c00}5\,$ divides both summands, the first because $\,\color{#c00}5\,$ divides one of $\,\rm\color{#c00}5\,\ \color{blue}{\rm consecutive\ integers}$.

As others said, it's Fermat's little theorem. One way to verify it in this particular case is to note that $$a^5 - a = a (a - 1)(a+1)(a^2 + 1)$$ If $a \equiv 0, 1$ or $4 \mod 5$, one of the first three factors is $0 \mod 5$. The other two possibilities are $a \equiv 2$ or $3 \mod 5$, in which case $a^2 + 1 \equiv 4 + 1 \equiv 0 \mod 5$. So in each case, $a^5 \equiv a \mod 5$.

A more general solution is the following:

Consider the multiplicative group $\mathbb{Z}_{p}^{\ast}$ of non-zero elements $\mod p$. This group has $p-1$ elements. Then for any element in the group, there is a cyclic subgroup $\langle g\rangle$. The order of this group is the order of $g$ which divides $p-1$, say the order is $k$ and $ak=p-1$. This means that $g^{p-1}=g^{ak}=(g^{k})^{a}\equiv 1^{a} \equiv 1 \mod p$. Multiplying again by $g$ you have that $g^{p}\equiv g \mod p$. That works for all the non-zero elements. It is obvious for the 0.

• This is essentially a proof of Fermat's little theorem. It works for any prime $p$ (of which 5 is one example). Mar 21, 2015 at 1:38