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.
 A: 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$
A: Hint: Inductive step: $$6^{k+1}-1=6\cdot 6^k-1=5\cdot 6^k +(6^k-1)$$
A: 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.
A: 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$.
A: 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)
$$
A: $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$. 
