Prove by mathematical induction that $31\mid5^{n+1}+6^{2n-1},\;$ $\forall n \in \mathbb{N}$ The proof of the statement $\mathcal{S}(n)=31\mid5^{n+1}+6^{2n-1}$ is going to be conducted by mathematical induction in terms of $n\in\mathbb{N}.$
1. Base clause
Show that $\mathcal{S}(1)$ holds.
$$\begin{align}\mathcal{S}(1)&=31\mid5^{1+1}+6^{2\cdot1-1}\\&=31\mid5^2+6\\&=31\mid25+6\\&=31\mid31\;\checkmark\end{align}$$
2. Induction hypothesis
Assume that $\mathcal{S}(n)$ holds for any fixed but arbitrary $n\in\mathbb{N}$.
3. Induction step
Show that $\mathcal{S}(n+1)$ holds.
$$ \begin{align} \mathcal{S}(n+1) & = 31\mid5^{(n+1)+1}+6^{2(n+1)-1} \\ & = 31\mid5^{n+2}+6^{2n+1} \\ & = 31\mid5^{n+1}\cdot5+6^{2n-1}\cdot6^2 \end{align} $$
At this point I don't know how to proceed. I really do have the feeling of missing something terribly obvious.
I tried to recreate the terms of the sum in the original statement $\mathcal{S}(n)$ with the goal of figuring out how to apply the induction hypothesis. 
At this point I am also aware that $$\mathcal{S}(n)\Leftrightarrow \exists\varphi\in\mathbb{N}:31\varphi=5^{n+1}+6^{2n-1}$$
and therefore 
$$\mathcal{S}(n+1)\Leftrightarrow \exists\varphi\in\mathbb{N}:31\varphi=5^{n+1}\cdot5+6^{2n-1}\cdot6^2$$

HINT: $$5^{n+2}+6^{2n+1}=5\cdot5^{n+1}+\underbrace{36}_{=5+31}\cdot6^{2n-1}=5\cdot(5^{n+1}+6^{2n-1})+31\cdot 6^{2n-1}$$
