# Prove that if $n$ is not divisible by $5$, then $n^4 \equiv 1 \pmod{5}$

Suppose $n$ is an integer which is not divisible by $5$. Prove that $n^4 \equiv 1 \pmod{5}$.

• As below posters have mentioned, you probably mean "divisible by 5" since integers that are not "divisors of 5" are just all integers except 1 and 5. Jul 19, 2014 at 0:33
• Exhaust the possible remainders of the quotient $n$ over $5$. Jan 5, 2015 at 22:11
• Cases $n=5k\pm 1$, $5k\pm 2$. Jan 5, 2015 at 22:12
• If $n$ is not divisible by $5$, then $n=5k+r$ for some integer $k$ and some $r\in\{1,2,3,4\}$. That gives you four cases to consider. Jan 5, 2015 at 22:12
• Hint $\ {\rm mod}\ 5\!:\,\ n\not\equiv 0\,\Rightarrow\, n\equiv \pm1,\pm2\,\Rightarrow\, n^4\equiv 1\ \$ Jan 5, 2015 at 22:33

$$n^4-1 = (n-1)(n+1)(n^2+1)$$ The factors $n-1$ and $n+1$ take care of $n \equiv \pm 1 \mod 5$, while if $n \equiv \pm 2 \mod 5$, $n^2 + 1 \equiv 2^2 + 1 \equiv 0 \mod 5$.

Product of 5 consecutive integer numbers is of course divisible by $5$, so $5|(n-2)(n-1)n(n+1)(n+2)$. If $5\not|n,$ then from primality of $5$ we have \begin{align*} 5|(n-2)(n-1)(n+1)(n+2) & = (n^2-1)(n^2-4)\\ & = n^4 - 5n^2 +4\\ & = n^4 - 1 - 5(n^2 - 1) \end{align*} so $5|n^4-1$.

• This is very neat. Jan 5, 2015 at 22:40

I would approach this with a proof by cases. There are $5$ options for $n\pmod{5}$:

Case $n\equiv 0\pmod 5$: Not possible by assumption.

Case $n\equiv 1 \pmod 5$: In this case, note that $n^4\equiv 1^4 \equiv 1 \pmod 5$

Case $n\equiv 2 \pmod 5$: (keep going--it's similar...)

Case ...

EDIT: this does assume that you meant "divisible," not "a divisor."

• Best proof in my opinion Jul 19, 2014 at 0:58
• Yes. Finally someone who isn't beating this to death with F.L.T. +1 Jul 19, 2014 at 18:50
• I actually prefer the FLT method because it's extensible, but that may just be me. It just didn't jump out at me this time. :) Jul 19, 2014 at 18:57
• To be fair, anorton is just verifying FLT with p=5. Jan 14, 2015 at 20:57

Fermat's little theorem states that if $$p$$ is prime, then for all $$n$$ with $$\gcd(n,p)=1$$, we have $$n^{p-1} \equiv 1 \mod p.$$ In your case we have $$p=5$$.

One proof: Because $$\gcd(n,p)=1$$ there is a number $$m$$ such that $$nm \equiv 1 \mod p$$. This means the map $$f(x)=nx$$ is a bijection on the set $$\{1,2,\dots, p-1\}$$ to itself since there is an inverse $$f^{-1}(x)=mx$$. Therefore,

$$1n \cdot 2 n\cdots (p-1)n = 1 \cdot 2 \cdots (p-1) \mod p$$

because the same set of numbers mod $$p$$ is being multiplied on each side. Rewrite

$$n^{p-1} (p-1)! \equiv (p-1)! \mod p$$

and cancel the $$(p-1)!$$ terms, which we can do because every number in $$\{1,2,\dots, p-1\}$$ is relatively prime to $$p$$ and has an inverse.

• Quite stellar. Only flaw is citing Wikipedia. Maybe I should go on Wikipedia right now and change that article to some utter nonsense, or better yet, put in some subtle mistake that could ensnare most novices. Jul 20, 2014 at 3:21
• I've reveiwed the Wikipedia article and couldn't find any mistakes in it. But that's no guarantee their isn't some mistake I missed, or that it won't get changed to something incorrect.
– user155234
Jul 21, 2014 at 21:16
• There's nothing wrong with wikipedia. The math articles are almost always useful. And if they are wrong, well isn't mathematics the queen of sciences because anyone can verify an argument? Jul 21, 2014 at 21:29
• @RobertSoupe Please see this meta discussion. It seems as though you are in the minority in this case. For more interesting reading, see this question. Jul 22, 2014 at 2:33
• @anorton Please note that I thought it was serious enough for me to comment but not serious enough for me to downvote. Maybe the math articles on Wikipedia are better than the history, politics and other such topics. But I just prefer to assume it's all wrong, the same way I assume all blue liquids are unsuitable to drink. If that puts me in a minority, oh well. I probably dislike Wikipedia for different reasons than math professors dislike Wikipedia. Jul 22, 2014 at 4:01

When $n\equiv 1\pmod{5}$, $n^4-1\equiv 1^4-1\equiv 0$.

When $n\equiv 2\pmod{5}$, $n^4-1\equiv 2^4-1=16-1=15\equiv 0$.

When $n\equiv 3\pmod{5}$, $n^4-1\equiv 3^4-1=81-1=80\equiv 0$.

When $n\equiv 4\pmod{5}$, $n^4-1\equiv 4^4-1=256-1=255\equiv 0$.

One way to get the result is to apply the Euler's theorem: $\varphi(5)=4$ and $\gcd(n,5)=1$ so $n^{4}\equiv 1\pmod 5$.

Hint

It suffices to consider the cases $n=1,2,3$ or $4$.

• Nice and short hint! Lovely avatar Sami. God bless her. :+) Jul 28, 2014 at 21:35

Also, you can prove that $5|n^5-n$ by induction on $n$ and from this conclude the claim.

Here's one particularly pretty way of proving this statement. It's nice because it uses combinatorics to prove an essentially number theoretic result. We start with the problem:

Suppose you want to make a necklace with $5$ beads, and you can paint each one of them with one of $n$ available colors. What's the number of different necklace you can have? (Necklace that can be obtained from other necklaces under rotation are considered the same)

We could stay that there are $n$ different ways to color the first bead, $n$ different ways to color the second, etcetera. But there are $5$ different rotations for each collar. Therefore the answer must be $\frac{n^5}{5}$, right? No, but close enough.

For instance, if all of the beads have only one color, then this necklace won't generate any other necklace under rotation. On the other hand, if a necklace has more than one color, then we affirm that it generates $5$ different necklaces (including itself). This is not an immediately obvious result so we shall prove it formally.

Indeed, let $(a_1,a_2,a_3,a_4,a_5)$ be a necklace, where $a_k$ is the color of the bead $k$. By assumption, there are $i,j \in \Bbb{Z}$ such that $a_i\neq a_j$ (consider the indices modulo $5$). Suppose we rotate the necklace by $r$ places. We affirm that $(a_1,a_2,...,a_5)=(a_{1+r},a_{2+r},...,a_{5+r})$ if and only if $r$ is a multiple of $5$. Suppose it's not, and $a_{i}=a_{i+r}$ for all $i$. Inductively, $a_i=a_{i+mr}$, for $m\in\Bbb{Z}$. But since we're looking at the indices modulo $5$, let $m=(j-i)\cdot r^{-1}$ where $r^{-1}$ is the inverse of $r$ modulo $5$ (it exists since $5$ is prime and $5\nmid r$). Then $a_i=a_{i+mr}=a_{i+(j-i)r^{-1}r}=a_j$ for all $i,j$. But we're assuming there are $i,j \in \Bbb{Z}$ such that $a_i\neq a_j$. Absurd.

Therefore the number of ways is actually $\frac{n^5-n}{5}+n$. The nice fact is that this number must be an integer (quite obviously), so in particular $\frac{n^5-n}{5}=\frac{n(n^4-1)}{5}$ is an integer. If $5\nmid n$, then $\gcd(5,n)=1$ since $5$ is prime, therefore $5\mid n^4-1\Rightarrow n^4\equiv 1 \pmod 5$. $\,\,\blacksquare$

• You might notice that throughout the proof we never really used any information about the number $5$ that distinguishes it from every other number. We only used the fact that it is a prime number. So you can pretty much exchange $5$ for $p$ prime and you get a proof of Fermat's Little Theorem. Jul 19, 2014 at 8:06

Like Timbuc,

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

$$=\underbrace{(n-2)(n-1)(n+1)(n+2)}+5(n-1)(n+1)$$

As $n$ must divide exactly one of any five consecutive integers and $5\nmid n,(5,n)=1,$

$n$ must divide one of the multiplicand underbrace

Here's a group theoretic perspective. The set of positive integers smaller than and relatively prime to $5$ form a group under multiplication mod $5$. If $n$ is not divisible by $5$ then $n$ is not congruent to $0$ mod $5$. Thus working mod $5$ we have $n$ is congruent to one of $\{1,2,3,4\}$ which is precisely the group mentioned above. The order of this group is $4$, and as a corollary to lagrange's theorem any member of the group raised to the $4^{th}$ power must be the identity element, namely $1$. Hence $n^4 \equiv 1$ mod $5$.

$n^{4}-1 = (n^{2}-1)(n^{2}+1)$ and (mod $5$) we have $n^{2}+1 \equiv n^{2} - 5n +6 = (n-2)(n-3),$ while also (mod $5$), we have $n^{2}-1 = (n-1)(n+1) \equiv (n-1)(n-4).$ Hence we have $(n^{4}-1) \equiv (n-1)(n-2)(n-3)(n-4)$ (mod $5$), and as long as $n$ is not divisible by $5$, one of $n-1,n-2,n-3,n-4$ is divisible by $5$.

$$n \equiv \pm 1 \space\mathrm{or} \pm 2 \pmod 5$$

Hence

$$n^4 \equiv (\pm 1)^4 \space\mathrm{or} \space(\pm 2)^4 \pmod 5 \\ \implies n^4 \equiv 1 \space\mathrm{or} \space 16 \pmod 5 \\ \therefore n^4 \equiv 1 \pmod 5$$

Fermat's little theorem provides an easy way.

But if you're not completely convinced, consider the squares modulo 5: $0, 1, 4, 4, 1$. Then the cubes: $0, 1, 3, 2, 4$. Then the fourth powers: $0, 1, 1, 1, 1$. Voila.

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

Since $\;n\neq0\pmod 5\;$, if it is $\;\pm1\pmod 5\;$ the above is $\;0\pmod 5\;$, and if it is $\;n=\pm 2\pmod 5\;$, then $\;n^2=(\pm2)^2=4\implies n^2+1=0\pmod 5\;$.

In any case, $\;n^4-1=0\pmod 5\;$