# 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. –  Evan W Jul 19 '14 at 0:33
Exhaust the possible remainders of the quotient $n$ over $5$. –  Git Gud Jan 5 at 22:11
Cases $n=5k\pm 1$, $5k\pm 2$. –  André Nicolas Jan 5 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. –  Brian M. Scott Jan 5 at 22:12
Hint $\ {\rm mod}\ 5\!:\,\ n\not\equiv 0\,\Rightarrow\, n\equiv \pm1,\pm2\,\Rightarrow\, n^4\equiv 1\ \$ –  Bill Dubuque Jan 5 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$.

-

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 –  frogeyedpeas Jul 19 '14 at 0:58
Yes. Finally someone who isn't beating this to death with F.L.T. +1 –  Mr.Fry Jul 19 '14 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. :) –  apnorton Jul 19 '14 at 18:57
To be fair, anorton is just verifying FLT with p=5. –  Dylan Yott Jan 14 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. –  Robert Soupe Jul 20 '14 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. –  Albert Jul 21 '14 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? –  nayrb Jul 21 '14 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. –  apnorton Jul 22 '14 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. –  Robert Soupe Jul 22 '14 at 4:01

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. –  Geoff Robinson Jan 5 at 22:40

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. :+) –  Babak S. Jul 28 '14 at 21:35

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

-

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

-

$$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\;$

-

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

-

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 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. –  Deathkamp Drone Jul 19 '14 at 8:06

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

-

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

-

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.

-