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.
$\begingroup$
$\endgroup$
8
-
2$\begingroup$ Isn't this a direct application of Fermat's Little Theorem? $\endgroup$– DeepakMar 21, 2015 at 1:23
-
$\begingroup$ Fermat's little theorem: en.wikipedia.org/wiki/Fermat%27s_little_theorem $\endgroup$– TravisJMar 21, 2015 at 1:24
-
4$\begingroup$ @Deepak Which is usually a hint that the OP doesn't know the theorem. $\endgroup$– Thomas AndrewsMar 21, 2015 at 1:25
-
$\begingroup$ possible duplicate of Purpose of Fermat's Little Theorem $\endgroup$– JMoravitzMar 21, 2015 at 1:26
-
$\begingroup$ @Deepak: Thomas got it right, I'd never heard of the theorem before. $\endgroup$– BobMar 21, 2015 at 1:28
|
Show 3 more comments
6 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
12
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$.
answered Mar 21, 2015 at 1:29
-
$\begingroup$ 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. $\endgroup$– tomaszMar 21, 2015 at 1:34
-
$\begingroup$ Only works for positive $n$. Can prove for negative in one step, though, from the positives, since $5$ is odd. :) $\endgroup$ Mar 21, 2015 at 1:35
-
$\begingroup$ This is nice, you just have to know that $\binom{p}{k}$ is divisible by $p$ for all $0<k<p$. $\endgroup$– TravisJMar 21, 2015 at 1:41
-
$\begingroup$ 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. $\endgroup$ Mar 21, 2015 at 1:44
-
1$\begingroup$ @Bob Note that all multiples of $5$ immediately reduce to $0$ modulo $5$. $\endgroup$– DeepakMar 21, 2015 at 2:17
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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}$.
answered Mar 21, 2015 at 2:09
$\begingroup$
$\endgroup$
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$.
answered Mar 21, 2015 at 1:33
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ This is essentially a proof of Fermat's little theorem. It works for any prime $p$ (of which 5 is one example). $\endgroup$– TravisJMar 21, 2015 at 1:38