# Alternate ways to prove that $4$ divides $5^n-1$

I was working for various method to solve this:

For all $n\in \mathbb N$: $4\;\mid\;(5^{n}-1)$.

My try was:

1st: $$n=1 \to 4|5^1-1\\n \geq 2 \to 5^n=25,125,625,3125,...\\ n\geq 2 \to 5^n=\overline{...a_4a_3a_225}\\=5+2(10)=100a_2+1000a_3+10^4a_4+...=\\25+100(a_2+10a_3+...)=25+100q\\{\color{Red}{5^n-1=25+100q-1=24+100q=4(6+25q)} }$$

2nd: divide into cases (even,odd) $$n=2k \to 5^n-1=5^{2k}-1=\overset{even}{(5^k-1)}\overset{even}{(5^k+1)}=\\2q*2q'=4qq' \to {\color{Blue} {4|5^{2k}-1}} \\n=2k+1 \to 5^n-1=5^{2k+1}-1 =5^{2k+1}-(5)+4\\=5*5^{2k}-5+4=5(5^{2k-1}-1)+4\\ \overset{{\color{Blue} {4|5^{2k}-1}}}{\rightarrow} =5(4qq')+4 =4q''$$

3rd: induction $$p_1:4|5^k-1\\p_k:4|5^k-1\\p_{k+1}:4|5^{k+1}-1\\$$ multiply R.H.S of $p_k$by 5 $$4|(5^k-1)*5 \to 4|5^{k+1}-5\\\left\{\begin{matrix} 4|{\color{Blue} {5^{k+1}-5}}\\ 4|4 \end{matrix}\right. \to 4|{\color{Blue} {5^{k+1}-5}} +4 \to 4|5^{k+1}-1$$

4th: we know $a^n-b^n=(a-b)(a^{n-1}b^0+a^{n-2}b^1+a^{n-3}b^2+...+a^0b^{n-1})$ so $$5^n-1=5^n-1^n=\\(5-1)(5^{n-1}+5^{n-2}+...+5^1+1)=\\4(5^{n-1}+5^{n-2}+...+5^1+1)=4q$$

5th: we know $(a+b)^n=\binom{n}{0}a^nb^0+\binom{n}{1}a^{n-1}b^1+\binom{n}{2}a^{n-2}b^2+...+\binom{n}{n-1}a^1b^{n-1}+\binom{n}{n}a^0b^n$ so $$5^n{\color{Magenta}{-1} }=(4+1)^n{\color{Magenta}{-1} }=\\\binom{n}{0}4^n+\binom{n}{1}4^{n-1}+\binom{n}{2}4^{n-2}+...+\binom{n}{n-1}4^1+\binom{n}{n}4^0 {\color{Magenta}{1} }=\\ \binom{n}{0}4^n+\binom{n}{1}4^{n-1}+\binom{n}{2}4^{n-2}+...+\binom{n}{n-1}4^1+1 {\color{Magenta}{-1} }=\\\binom{n}{0}4^n+\binom{n}{1}4^{n-1}+\binom{n}{2}4^{n-2}+...+\binom{n}{n-1}4^1=\\ 4(\binom{n}{0}4^{n-1}+\binom{n}{1}4^{n-2}+\binom{n}{2}4^{n-3}+...+\binom{n}{n-1})=4q$$

6th: $$5\equiv 1 (mod 4)\\5^n\equiv 1^n (mod 4)\\5^n\equiv 1 (mod 4)\\ \to 5^n-1\equiv 0 (mod 4)$$

7th: $$f(x)=x^n-1\\$$divide by $x-1$ so $$x^n-1=(x-1)q(x)+R$$finding remainder by putting $x=1 \to r=0$
so,in division of $f(x)$ to $x-1$ remainder is zero now put $x=5$ in f(x) $$f(5)=5^n-1=(5-1)Q(5) \to =4q$$

8th: we know $4|4$ it is possible to multiply right side by any integer $$4|4 \to 4|4*(5^{n-1}+5^{n-2}+5^{n-3}+...+5^{1}+5^{0})\\4|{\color{Red} {(5-1)}}*(5^{n-1}+5^{n-2}+5^{n-3}+...+5^{1}+5^{0})\\4|5^n-1$$

9th: If $a$ divide by $b$ we can write $a=bq+r , 0\leq r <b$ . then it is easy to proof by induction that $$a^n=b^nq'+r^n$$ so ,in division of $5$ by $4$ we have $$5=4q+1\\5^n=4q'+1^n\\ \to 5^n-1^n=4q'$$

Now I am looking for other proofs. Maybe:

${\color{Red} {Argue \space by \space contradiction}}$
formulate and equivalent problem
choose effective notation
work backward
generalize
draw a figure
or any other idea

• You have $9$ ways to prove it and you want more?! – 6005 Aug 3 '15 at 22:27
• Why not just learn how to calculate in the ring $\mathbb{Z}/4\mathbb{Z}$? In this ring $5 = 1$ and that's that! – Rob Arthan Aug 3 '15 at 22:34
• @RobArthan that was his approach #6. – JMoravitz Aug 3 '15 at 22:35
• The "reason" to bother with various arguments is that they may reveal connections among the methods at a deeper level. Many of the proofs here amount to different ways of "saying the same thing", but may offer alternative interpretations of these approaches to the problem. – colormegone Aug 4 '15 at 0:52
• Or, to quote Michael Atiyah: I think it is said that Gauss had ten different proofs for the law of quadratic reciprocity. Any good theorem should have several proofs, the more the better. For two reasons: usually, different proofs have different strengths and weaknesses, and they generalise in different directions - they are not just repetitions of each other. – Krijn Aug 4 '15 at 0:59

Algebraic proof:

Consider the field $K:=\mathbb{F}_{5^n}$. We shall show that the group of units $K^\times =K\setminus\left\{0\right\}$ has a subgroup $H$ of order $4$. By Lagrange's Theorem, $4$ must then divide the order of $K^\times$, which is $5^n-1$. Now, this group $H$ is given by the subset $\{1,2,3,4\}=\mathbb{F}_5\setminus\{0\}$. The result follows immediately.

Suppose there exists $n\in\mathbb{N}$ such that $4\nmid 5^n-1$. Then, choose $n$ to be the smallest. Clearly, $n>1$. Now, $4\mid 5^{n-1}-1$ as $n-1\in\mathbb{N}$ and $n-1<n$. Hence, $4\mid 5\left(5^{n-1}-1\right)=5^n-5$. Consequently, $4\mid \left(5^n-5\right)+4=5^n-1$, which contradicts the choice of $n$.

• Sort of overkilling the problem, isn't it? – Batominovski Aug 3 '15 at 23:11

Let there be $5$ different characters $\{\_\ , a,b,c,d\}$ to form a string of length $n$. There are $5^n$ of those strings.

Apart from the string of all $\_$'s $"\_\ \_\ \_\ldots \_"$, all other strings can be grouped into exactly one of four groups in this way:

Take the first character along each string that is not an $\_$, which can be one of $a,b,c$ or $d$.

Group all strings according to their respective first non-$\_$ character. For example the string $"\_\ \_\ b\ \_\ c\ldots a"$ is in group $b$.

By symmetry, the groups $a$, $b$, $c$ and $d$ should have the same number of strings. So the number of all $n$-character string is $4k+1$.

• Is this a proof by concept of combination? – Khosrotash Aug 3 '15 at 22:44
• @Khosrotash The common phrase in english for this style of proof is "combinatorial proof" as opposed to "proof by concept of combination" – JMoravitz Aug 3 '15 at 22:46

Using base-$5$, this is pretty obvious: $$10^n_5 - 1 = \underbrace{444\ldots4_5}_n = 4\times \underbrace{111\ldots 1_5}_n$$

• Cool, I think this solution shows nicely intuitively that actually: For all $n,m\in \mathbb N$: $m\;\mid\;((m + 1)^{n}-1)$. right? – Ivo Beckers Aug 4 '15 at 11:59

Look at the following for $n = 2$:

$$\bullet \bullet \bullet \bullet \diamond \\ \bullet \bullet \bullet \bullet \bullet \\ \bullet \bullet \bullet \bullet \bullet \\ \bullet \bullet \bullet \bullet \bullet \\ \bullet \bullet \bullet \bullet \bullet$$

The black dots visualize $5^2 - 1$. Now one easily sees a division of this in sets of $4$ and therefore it is divisible by $4$. We can use the same argument for $n = 3$. Unfortunately, we cannot 'see' higher dimensions. However we can then solve this by induction. In the case where $n = 3$, we have a $4 \times 5 \times 5$ cube and an extra side that is exactly the $n=2$ case. The same holds for $n= 4$, we get a hypercube with a corner removed, which is actually a $4 \times 5 \times 5 \times 5$ hypercube with the $n = 3$ case added to create a $5 \times 5 \times 5 \times 5$ hypercube with a corner missing.

With induction, this holds for all $n \in \mathbb{N}$

• +1. It would be better to also prove the base case $n=1$, and the induction step from $n=1$ to $2$ is easier to visualise. – peterwhy Aug 4 '15 at 8:25

In the $n$-dimensional vector space $F_5^n$, every non-zero vector generates a one-dimensional vector space with 5 elements. Each pair of such vector spaces intersect only at the zero vector.

Therefore, $F_5^n$ can be divided into one-dimensional sub-spaces (all containing the zero vector). If the zero vector is removed, we have partitioned remaining $5^n-1$ elements of $F_5^n$ into subsets of size 4.

This somewhat relates to point 8 in the question, but the presentation is very different.

For the geometric series below we have:

$$1+5+5^2+\cdots+5^{n-1}=\frac{5^n-1}{5-1}=\frac{5^n-1}{4}$$

The LHS is a sum of integers, so the RHS must be an integer. Then $5^n-1$ must be a multiple of $4$.

"Drawing a figure" is a bit tricky for higher dimensions, but one could consider expanding an "$n-$ cube" with "edge length" of 4 . To make it a bit easier to work with, we would extend each "edge" by $\ \frac {1}{2} \$ in both "directions", rather than simply adding 1 .

For a line segment , we have $\ 4 \ = \ 5 \ - \ 2 \ \cdot \ \frac{1}{2} \$ , the subtracted term representing the "missing" segments of length $\ \frac{1}{2} \$ at either end of the segment of length 4 .

For a square, we add 4 rectangles of length 4 and width $\ \frac{1}{2} \$ , leaving squares of dimensions $\ \frac{1}{2} \ \times \ \frac{1}{2} \$ "unfilled" at each of the four vertices, or

$$4^2 \ + \ 4 \ (4 \cdot \frac{1}{2} ) \ = \ 5^2 \ - \ 4 \ \cdot \left(\frac{1}{2}\right)^2 \ \ .$$

For a cube, we need to add 6 parallelopipeds of area $\ 4 \ \times \ 4 \$ and "thickness" $\ \frac{1}{2} \$ , 12 of length 4 and cross-section $\ \frac{1}{2} \ \times \ \frac{1}{2} \$ , leaving 8 "unfilled" cubes of edge $\ \frac{1}{2} \$ at the vertices, or

$$4^3 \ + \ 6 \ (4 \cdot \ 4 \cdot \frac{1}{2} ) \ + \ 12 \ (4 \cdot \ \frac{1}{2} \cdot \frac{1}{2} ) \ = \ 5^3 \ - \ 8 \ \cdot \left(\frac{1}{2}\right)^3 \ \ .$$

A 4-hypercube requires 8 4-volumes of dimensions $\ 4^3 \ \times \ \frac{1}{2} \$ , 24 of dimensions $\ 4^2 \ \times \ \left(\frac{1}{2}\right)^2 \$ , and 32 of dimensions $\ 4 \ \times \ \left(\frac{1}{2}\right)^3 \$ , leaving "unfilled" 4-hypercubes of 4-volume $\ \left(\frac{1}{2}\right)^4 \$ at its 16 vertices, thus

$$4^4 \ + \ 8 \ (4 \cdot 4 \cdot 4 \cdot \frac{1}{2} ) \ \ + \ 32 \ (4 \cdot 4 \cdot \frac{1}{2} \cdot \frac{1}{2} ) + \ 12 \ (4 \cdot \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} )$$ $$= \ 5^4 \ - \ 16 \ \cdot \left(\frac{1}{2}\right)^4 \ \ , \ \ \text{or} \ \ 256 \ + \ 256 \ + \ 96 \ + \ 16 \ = \ 625 \ - \ 1 \ \$$

[and so on] .

The hypervolumes are all multiples of 4 , so the sum of the terms on the left-hand side is as well. The "coefficients" for the $\ n-$ hypercube are discussed, for instance, here .

EDIT: I'll admit I was "taking a flier" on this argument, because I wasn't familiar enough with the higher dimensional generalization for a cube. (But the point of trying something new is to see what one might learn -- and I've got an awful lot to learn...)

The sum of the various hypervolumes proves to be

$$\ \sum_{m=1}^n \ \left[ 2^{n - m} \ \binom{n}{m} \right] \ \cdot \ 4^m \ \left( \frac{1}{2} \right)^{n-m} \ = \ \sum_{m=1}^n \ \ \binom{n}{m} \ \cdot \ 4^m \ \ ,$$

which is the sum in Khosrotash's 5th proof. (The $\ m = 0 \$ term omitted is the product of the number $\ 2^n \$ of little hypercubes at the vertices of the big hypercube times their volume $\ \left( \frac{1}{2} \right)^n \$ , for a total hypervolume of 1 .)

• I accept the implied criticism of the "downvote": on thinking about this again, I realized I hadn't really shown what that the sum on the left would in fact produce the correct sum. I learned something about hypercube volumes that does link this to some of the other given proofs. – colormegone Aug 4 '15 at 1:38