1
$\begingroup$

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.

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

6 Answers 6

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
12
  • $\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$
    – tomasz
    Mar 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$
    – TravisJ
    Mar 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$
    – Deepak
    Mar 21, 2015 at 2:17
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

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

You must log in to answer this question.

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