Prove by induction that for all $n$, $8$ is a factor of $7^{2n+1} +1$ I want to prove by induction that for all $n$, 8 is a factor of $$7^{2n+1}+1$$
I have proved it true for the base case and assumed it true for $n=k$, but when I cannot figure out when to go towards the end of proving it true for $n=k+1$ assuming it is true for $n=k$.
I let $$7^{2k+1}+1 = 8m$$
Then I work with $$7^{2(k+1)+1}+1$$ to get eventually $$7^2(8m)$$
I am not sure if this is correct or if it is I am not sure how to prove that this too is dividable by $8$.
I would appreciate any help.
Thanks
 A: Below I explain how the nonmodular inductive proofs in other answers are really just applications of modular arithmetic product rules. Indeed, let's examine closely the inductive step
$\qquad\qquad\quad\!  8\mid \overbrace{(7^{\large 2n+1}\!+1)}^{\large\rm P(n)},\quad\   8\mid (7^{\large 2} - 1)$ 
$\qquad\ \ \ \Rightarrow\ \ 8\mid (7^{\large 2n+1}\!+\color{#c00}1)\,\color{#0a0}{7^{\large 2}}\color{#c00}{-1}\,(\color{#0a0}{7^{\large 2}}-1)\, =\, \smash{\overbrace{7^{\large 2n+3}-1}^{\large\rm P(n+1)}}\ \ $ is a special case of Proof below 
$\begin{eqnarray}
\rm {\bf Lemma}\ \   &\rm m\ \ |&\rm\ \, X\!-\!x\quad\  \& &&\rm\! m\ |\: Y\!-\!y \ \Rightarrow\ m\:|\!\!&&\rm XY - \: xy\ \ \ \, {\bf [Divisibility\ Product\ Rule]} \\[.3em]
\rm {\bf Proof}\ \ \ \ \ &\rm m\ \ |&\rm (X\!-\!\color{#c00}x)\:\color{#0a0}Y\  \,+   &&\rm\, \color{#c00}x\ (\color{#0a0}Y\!-\!y)\ \ \ \ = &&\rm XY - \: xy \\[.5em]
\rm {\bf Lemma}\ \ &         &\rm\ \, X\equiv x\quad\ \  \& &&\rm\quad\  Y\equiv y \ \ \ \ \Rightarrow\ &&\rm XY\equiv xy \ \ \ \, {\bf [Congruence\ Product\ Rule]}\\[.3em]
\rm {\bf Proof}\ \ \ \ \ &0\equiv& \rm (X\!-\!\color{#c00}x)\:\color{#0a0}Y\,\   + &&\rm\, \color{#C00}x\ (\color{#0a0}Y\!-\!y)\ \ \ \ \equiv &&\rm XY - \: xy \\
\end{eqnarray}$ 

If congruences are known, then we may simply quickly apply the Congruence Product Rule
$\qquad \color{#c00}{7^{\large 2n+1}\equiv -1},\ \ \color{#0a0}{7^{\large 2}\equiv 1}\,\Rightarrow\, 7^{\large 2n+3}= \color{#c00}{7^{\large 2n+1}}\color{#0a0}{ 7^{\large 2}}\equiv \color{#c00}{(-1)}\color{#0a0}{(1)}\equiv -1\pmod 8$
Thus, with the help of modular language, we see that the induction simplifies to the trivial induction that $\, a\equiv 1\,\Rightarrow\, a^n\equiv 1\,$ (here $\,\color{#0a0}{a = 7^2}).\,$ Or, $\,7\equiv -1\,\Rightarrow\, 7^n\equiv (-1)^n\equiv -1$ for odd $\,n\,$ by the Congruence Power Rule, which abstracts such iterated applications of the Product Rule. 
So the nonmodular proofs can be viewed as the result of compiling the higher-level (congruence) language proofs into  lower-level (divisibility) assembly language. One can do such compilation mechanically for any such congruence proof. Just as for software, the low-level assembly language is far less comprehensible since it eliminates  higher level conceptual structure - which often leads to great simplification, e.g $\,a\equiv 1\,\Rightarrow\,a^n\equiv 1\,$ above.
Also worth mention is that this proof can be discovered mechanically, i.e. without any required insight, be using the method of multiplicative telescopy.
A: Inductive step
$$7^{(2(n+1)+1)}+1=7^{(2n+1+2)}+1=49\times\left(7^{(2n+1)}+1\right)-8\times 6$$
A: Hint:
$$7^{2(n+1)+1}+1=49\cdot\left(7^{2n+1}+1\right)-48\implies\ldots$$
A: Your approach was right until you considered $7^{2k+1}+1=8m$
$49 \times 7^{2k+1} + 1 = 49 \times(8m-1) +1 = 8 \times 49m -48$ which is divisible by 8.
A: use modules...
$7 \equiv -1 \pmod 8$, so $$7^{2n + 1} + 1 \equiv (-1)^{2n + 1} + 1 \equiv -1 + 1 \equiv 0 \pmod 8$$ so it is divisble by $8$
(Note that $2n + 1$ is odd, so $(-1)^{2n+1} = -1$)
A: Hint.-$$7=8-1\Rightarrow 7^{2n+1}=8M-1\Rightarrow7^{2n+1}+1=8M$$
