3
$\begingroup$

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

$\endgroup$
  • 16
    $\begingroup$ You have $9$ ways to prove it and you want more?! $\endgroup$ – 6005 Aug 3 '15 at 22:27
  • 2
    $\begingroup$ Why not just learn how to calculate in the ring $\mathbb{Z}/4\mathbb{Z}$? In this ring $5 = 1$ and that's that! $\endgroup$ – Rob Arthan Aug 3 '15 at 22:34
  • 1
    $\begingroup$ @RobArthan that was his approach #6. $\endgroup$ – JMoravitz Aug 3 '15 at 22:35
  • 2
    $\begingroup$ 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. $\endgroup$ – colormegone Aug 4 '15 at 0:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Krijn Aug 4 '15 at 0:59
13
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Sort of overkilling the problem, isn't it? $\endgroup$ – Batominovski Aug 3 '15 at 23:11
17
$\begingroup$

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

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

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

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

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

$\endgroup$
  • $\begingroup$ +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. $\endgroup$ – peterwhy Aug 4 '15 at 8:25
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – colormegone Aug 4 '15 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.