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

Question

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

Answer 1

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.

---

Proof by Contradiction

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

"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 .)

Answer 6

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.

Answer 7

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