# Proving $6^n - 1$ is always divisible by $5$ by induction

I'm trying to prove the following, but can't seem to understand it. Can somebody help?

Prove $6^n - 1$ is always divisible by $5$ for $n \geq 1$.

What I've done:

Base Case: $n = 1$: $6^1 - 1 = 5$, which is divisible by $5$ so TRUE.

Assume true for $n = k$, where $k \geq 1$: $6^k - 1 = 5P$.

Should be true for $n = k + 1$

$6^{k + 1} - 1 = 5Q$

$= 6 \cdot 6^k - 1$

However, I am unsure on where to go from here.

For $n\geq 1$, let $S(n)$ denote the statement $$S(n) : 5\mid(6^n-1)\Longleftrightarrow 6^n-1=5m, m\in\mathbb{Z}.$$ Base case ($n=1$): $S(1)$ says that $5\mid(6^1-1)$, and this is true.

Inductive step: Fix some $k\geq 1$ and assume that $S(k)$ is true where $$S(k) : 5\mid(6^k-1)\Longleftrightarrow 6^k-1=5\ell, \ell\in\mathbb{Z}.$$ To be proved is that $S(k+1)$ follows where $$S(k+1) : 5\mid(6^{k+1}-1)\Longleftrightarrow 6^{k+1}-1=5\eta, \eta\in\mathbb{Z}.$$ Beginning with the left-hand side of $S(k+1)$, \begin{align} 6^{k+1} - 1 &= 6^k\cdot 6-1\tag{by definition}\\[0.5em] &= (5\ell+1)\cdot 6-1\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &= 6\cdot 5\ell+5\tag{expand}\\[0.5em] &= 5(6\ell+1)\tag{factor out $5$}\\[0.5em] &= 5\eta.\tag{$\eta=6\ell+1; \eta\in\mathbb{Z}$} \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.

Thus, by mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$

• Perfect! This has definitely made a things alot clearer! – RandomMath Apr 17 '15 at 14:56
• @RandomMath Glad it helped. :) You may want to look at this list for some other useful questions/answers of mine on induction that may prove useful to you. I love induction a little bit too much (uname actually used to be induktio). Most of it is because I, like you, struggled a lot with it. Keep whacking away at induction proofs though, and you'll master them before long. :) – Daniel W. Farlow Apr 17 '15 at 14:58
• I want to mention that any a^k - 1 divisible by a-1 – TigerTV.ru Jan 6 '19 at 20:24

Hint: Inductive step: $$6^{k+1}-1=6\cdot 6^k-1=5\cdot 6^k +(6^k-1)$$

• The inductive step is where I'm confused on on this question, could you elaborate on how you got to this? – RandomMath Apr 17 '15 at 14:35
• @RandomMath Since obviously $5\mid 5\cdot 6^k$ and by the inductive hypothesis $5\mid 6^{k}-1$, can you see that $5\mid 6^{k+1}-1$? And the equalities here only use trivial algebraic manipulations. – user26486 Apr 17 '15 at 14:35
• @RandomMath From your question description it seems you know you want to prove $5\mid 6^{k+1}-1$ assuming $5\mid 6^k-1$. You began by showing $6^{k+1}-1=6\cdot 6^{k}-1$. What I suggest here is continuing the equality with $6\cdot 6^{k}-1=5\cdot 6^{k}+(6^k-1)$, which makes it clear that we indeed have $5\mid 6^{k+1}-1$ (assuming $5\mid 6^{k}-1$). – user26486 Apr 17 '15 at 14:43
• Yes that is what im trying to prove. However, im struggling to get my head around how to get from 6(6^k) -1 to 5*6^k + (6^k -1) – RandomMath Apr 17 '15 at 14:45
• @RandomMath $6\cdot 6^{k}-1=(5+1)\cdot 6^k-1=5\cdot 6^k + 6^k-1=5\cdot 6^k +(6^k-1)$. – user26486 Apr 17 '15 at 14:46

In comments you ask about the source of the following standard proof of the inductive step $$5\mid 6^k-1\ \Rightarrow\ \color{#c00}5\cdot 6^k +(6^k\!-1)\,=\, \color{#0a0}{6^{k+1}-1}$$

This is a very natural question since such proofs often appear to be pulled out of a hat, like magic. There is, in fact, a good general explanation for their source. Namely such proofs are simply special cases of the proof of the Congruence Product Rule, as we show below.

${\bf Claim}\rm\qquad\ 6\equiv 1,\, 6^{k}\!\equiv 1 \Rightarrow\ 6^{k+1}\!\equiv 1\ \ \ \pmod{\!5},\$ a special case of the following

${\bf Lemma}\rm\quad\ \, A\!\equiv a,\, B\!\equiv b\ \Rightarrow\ AB\equiv ab\ \pmod{\!n}\ \ \$ [Congruence Product Rule]

${\bf Proof}\ \ \ \rm n\mid A\!-\!a,\,\ B-b\,\Rightarrow\, n\mid ( A\!-\!a) B +a\ (B\!-\!b) =A B\,-\,ab$

$\rm\ \ \ \ e.g.\ \ \ 5\mid\ 6\!-\!1,\,\ 6^{k}\!-\!1\ \Rightarrow\ 5\mid(\color{#c00}{6\!-\!1})\,6^{k}+ 1\,(6^{k}\!\!-\!1) = \color{#0a0}{6^{k+1}\!-1}$

Notice that the prior inference is precisely the same as said standard proof of the inductive step. Thus we see that this inference is simply a special case of the proof of the Congruence Product Rule. Once we know this rule, there's no need to repeat the entire proof every time we need to use it. Rather, we can simply invoke the rule as a Lemma (in divisibility form if congruences are not yet known). Then the inductive step has vivid arithmetical structure, being the computation of a product $\, 6\cdot 6^{k}\equiv 6^{(k+1)}.\,$ No longer is the innate arithmetical structure obfuscated by the details of the proof - since the proof has been encapsulated into a Lemma for convenient reuse.

In much the same way, congruences often allow one to impart intuitive arithmetical structure onto complicated inductive proofs - allowing us to reuse our well-honed grade-school skills manipulating arithmetical equations (vs. more complex divisibility relations). Often introduction of congruence language will serve to drastically simplify the induction, e.g. reducing it to a trivial induction such as $\, 1^n\equiv 1,\,$ or $\,(-1)^{2n}\equiv 1.\,$ The former is the essence of the matter above.

• +1 for taking the time and effort to put that up and for clearly wanting to help OP. I hope s/he reads it. – Daniel W. Farlow Apr 17 '15 at 15:46

We can show by induction that $6^k$ has remainder $1$ after division by $5$.

The base case $k=1$ (or $k=0$) is straightforward, since $6=5\cdot 1+1$.

Now suppose that $6^k$ has remainder $1$ after division by $5$ for $k\ge 1$. Thus $6^k = 5\cdot m+1$ for some $m \in \mathbb{N}$. We can then see that $$6^{k+1}=6\cdot 6^{k} = (5+1)(5\cdot m +1) = 5^2 \cdot m + 5 + 5\cdot m + 1$$ $$=5(5\cdot m + m + 1) + 1.$$

Thus $6^{k+1}$ has remainder $1$ after division by $5$.

Therefore for every $k$, we can write $6^k = 5\cdot m +1$ for some $m$.

• Once we have established that every power of $6$ has remainder of $1$ after division by $6$, the rest of the problem follows after subtracting $1$ from $6^k$. – Joel Apr 17 '15 at 14:44

This is the inductive step written out: $$6 \cdot 6^k - 1 = 5 \cdot Q |+1; \cdot \frac{1}{6};-1 \Leftrightarrow 6^k - 1 = \frac{5\cdot Q-5}{6}\underset{P}{\rightarrow}5\cdot P = \frac{5\cdot Q - 5 }{6} | \cdot \frac{1}{5}; \cdot 6\Leftrightarrow Q=6\cdot P + 1$$ $$6^k - 1 = \frac{5\cdot Q-5}{6} \overset{Q}{\rightarrow}\ (6^k-1 = \frac{5\cdot (6\cdot P + 1)-5}{6}\Leftrightarrow 6^k-1 = 5\cdot P)$$

• Please, use $LATEX$. – ً ً Sep 10 '16 at 23:17
• I tried this codecogs.com/latex/eqneditor.php However i am not sure whether this is correct LaTex – Martin Erhardt Sep 10 '16 at 23:18
• Just put $\$$starting from every line and at the end of every line. – ً ً Sep 10 '16 at 23:22 • ah thanks, I am new here – Martin Erhardt Sep 10 '16 at 23:28$6$has a nice property that when raised to any positive integer power, the result will have$6$as its last digit. Therefore, that number minus$1$is going to have$5$as its last digit and thus be divisible by$5\$.

• OP wants to prove this by induction – Shailesh Sep 10 '16 at 23:56
• it's works for another numbers not only for 6. – TigerTV.ru Jan 6 '19 at 20:52