Proving that $6^{2n+1} + 1$ is divisible by $7$ for $n\geq 1$ by induction How should I go about solving a problem like this using induction?
Would I:
First test $(n = 1)$ so that $6^{2(1)+1} + 1 = 6^3 + 1 = 217/7 = 31$.
Then assume $(n = k)$ so that you have $6^{2(k) + 1} + 1$
Then $(n = k+1)$ and substitute in so it is $6^{2(k+1)+1}+1$.
Where should I go from here to prove this? Or what should I do with my past steps to correct what I've already done?
 A: By assumption, $6^{2(k) + 1} + 1$ is divisible by $7$, so $6^{2(k) + 1} \equiv -1 \mod7$.
On the other hand, $6^{2(k+1) + 1} = 6^{(2k+1) + 2}=36*6^{2(k) + 1}\equiv (1)(-1) \mod 7 \equiv -1 \mod 7$.
Hence $6^{2(k+1) + 1} + 1$ is divisible by $7$.
A: For $n=1$ we have $6^{2n+1} + 1 = 6^{3} +1,$
so $7 \mid (6^{2n+1} + 1).$
If $n \geq 1$ is such that
$$6^{2n+1} = 7k - 1$$
for some $k \geq 1,$
then
$$6^{2n+3} + 1 = 36\cdot 7k - 36 + 1 = 36\cdot 7k - 35=7(36k-5),$$
divisible by 7.
A: Hint $\ $ The inductive step can be intuitively viewed as congruence multiplication
$$ \begin{align}{\rm mod}\,\ 7\!:\qquad \color{}{36}\  \equiv&\,\ \  \color{}{1}\\[2pt] 
6\cdot 36^{\color{#c00}n}\equiv&\,\ {-}1\ \ \ {\rm i.e.}\ \  P(\color{#c00}n)\\[-4pt]
\overset{\rm multiply}\Rightarrow\ \ 6\cdot 36^{\color{#0a0}{n+1}} \equiv&\,\  {-}1\ \ \ {\rm i.e.}\ \ P(\color{#0a0}{n\!+\!1})\end{align}\ \qquad $$
If congruences are unfamiliar then you can eliminate them as described in this answer.
A: I'll outline an answer that does not rely on modular arithmetic; it is very similar to Chou's answer but with the details more spelled out. 

For $n\geq 1$, let $S(n)$ denote the statement
$$
S(n) : 7\mid(6^{2n+1}+1)\Longleftrightarrow 6^{2n+1}+1=7m, m\in\mathbb{Z}.
$$
Base case ($n=1$): $S(1)$ says that $7\mid(6^{2(1)+1}+1)$, and this is true since $6^3+1=217$ and $217=7\cdot 31$. 
Inductive step: Fix some $k\geq 1$ and assume that $S(k)$ is true where
$$
S(k) : 7\mid(6^{2k+1}+1)\Longleftrightarrow 6^{2k+1}+1=7\ell, \ell\in\mathbb{Z}.
$$
To be proved is that $S(k+1)$ follows where
$$
S(k+1) : 7\mid(6^{2k+3}+1)\Longleftrightarrow 6^{2k+3}+1=7\eta, \eta\in\mathbb{Z}.
$$
Beginning with the left-hand side of $S(k+1)$,
\begin{align}
6^{2k+3}+1 &= 6^2\cdot6^{2k+1}+1\tag{by definition}\\[0.5em]
&= 36(6^{2k+1}+1)-35\tag{rearrange}\\[0.5em]
&= 36(7\ell)-7\cdot 5\tag{by $S(k)$, the ind. hyp.}\\[0.5em]
&= 7(36\ell-5)\tag{factor out $7$}\\[0.5em]
&= 7\eta,\tag{$\eta=36\ell-5; \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$
