Proving that $19\mid 5^{2n+1}+3^{n+2} \cdot 2^{n-1}$ How can I prove that $$5^{2n+1}+3^{n+2} \cdot 2^{n-1} $$ can be divided by 19 for any nonnegative n? What modulo should I choose?
 A: Its arithmetical essence is clarified using Congruence Product and Power Rules, namely
$$\begin{align}{\rm mod}\,\ 19\!:\qquad \big[\,\  5^{\large\color{#c00}1} \ &\equiv\, -3^{\large\color{#c00} 2}\ \cdot\, 2^{\large\color{#c00}{-1}}\big]\ \ \ {\rm by}\ \ \ \ \,2\cdot 5\equiv -3^{\large 2}\\
 \times\ \ \, \big[\, 5^{\large 2n} &\equiv\ \ \  3^{\large n}\,\cdot\, 2^{\large n}\ \ \ \big]\ \ \ {\rm by} \ \ \Big[\,5^{\large 2}\equiv 3\cdot 2\,\Big]^{\large n}\\[.1em]
\Rightarrow\,\ 5^{\large 2n+\color{#c00}1}\!&\equiv -3^{\large n+\color{#c00}2} 2^{\large n\color{#c00}{-1}}
\end{align}\qquad\qquad\quad\ $$
Therefore we infer that $\ 19\mid 5^{\large 2n+1}+\ 3^{\large n+2} 2^{\large n-1}$ when it is integral, i.e. for all $\,n\ge 1$
Remark $ $ It is even clearer when written in fractional form, namely
$$ \dfrac{5^{\large 2n+1}}{3^{\large n+2}2^{\large n-1} }\ \equiv\ \left[\dfrac{2\cdot 5}{3\cdot 3}\right]\left[\dfrac{5^{\large 2}}{3\cdot 2}\right]^{\large n}\!\!\equiv\,  -1\cdot 1^{\large n}\equiv\, -1$$
Notice how use of congruence language greatly simplifies the inductive step, reducing it to the trivial induction that $\,1^n\equiv 1.$
A: You can prove this by induction.

First, show that this is true for $n=1$:
$5^{2\cdot1+1}+3^{1+2}\cdot2^{1-1}=19\cdot8$
Second, assume that this is true for $n$:
$5^{2n+1}+3^{n+2}\cdot2^{n-1}=19k$
Third, prove that this is true for $n+1$:
$5^{2(n+1)+1}+3^{n+1+2}\cdot2^{n+1-1}=$
$5^{2+2n+1}+3^{1+n+2}\cdot2^{1+n-1}=$
$5^{2}\cdot5^{2n+1}+3^{1}\cdot3^{n+2}\cdot2^{1}\cdot2^{n-1}=$
$5^{2}\cdot5^{2n+1}+3^{1}\cdot2^{1}\cdot3^{n+2}\cdot2^{n-1}=$
$25\cdot5^{2n+1}+\color\green{6}\cdot3^{n+2}\cdot2^{n-1}=$
$25\cdot5^{2n+1}+(\color\green{25-19})\cdot3^{n+2}\cdot2^{n-1}=$
$25\cdot5^{2n+1}+25\cdot3^{n+2}\cdot2^{n-1}-19\cdot3^{n+2}\cdot2^{n-1}=$
$25\cdot(\color\red{5^{2n+1}+3^{n+2}\cdot2^{n-1}})-19\cdot3^{n+2}\cdot2^{n-1}=$
$25\cdot\color\red{19k}-19\cdot3^{n+2}\cdot2^{n-1}=$
$19\cdot25k-19\cdot3^{n+2}\cdot2^{n-1}=$
$19\cdot(25k-3^{n+2}\cdot2^{n-1})$

Please note that the assumption is used only in the part marked red.
A: For $n=0$, the formula says that $\left.19\middle|\frac{19}2\right.$, which is false. So consider $n\ge1$:
$$
\begin{align}
5^{2n+1}+3^{n+2}2^{n-1}
&=125\cdot25^{n-1}+27\cdot6^{n-1}\\
&\equiv11\cdot6^{n-1}+8\cdot6^{n-1}&\pmod{19}\\
&=19\cdot6^{n-1}\\
&\equiv0&\pmod{19}
\end{align}
$$
Since
$$
\begin{align}
125&\equiv11&\pmod{19}\\
25&\equiv6&\pmod{19}\\
27&\equiv8&\pmod{19}
\end{align}
$$
A: Denote $\mathcal{P}(n)$ the statement that $5^{2n+1} + 3^{n+2}\cdot 2^{n-1}$ is divisible by $19$. You can check for yourself that $\mathcal{P}(1)$ is true. A setup for the proof of $\mathcal{P}(n+1)$:
\begin{align} 
5^{2(n+1)+1} + 3^{(n+1)+2}\cdot 2^{(n+1)-1} & = \\
25 \times 5^{2n+1} + 6 \times 3^{n+2}\cdot 2^{n-1}  & = \\
19 \times 5^{2n+1} + 6 \times 5^{2n+1} + 6 \times 3^{n+2}\cdot 2^{n-1} & = \cdots
\end{align} can you finish the proof from here?
A: $2^{n-1} = \frac12 2^n \equiv 10 \cdot 2^n \pmod {19}$. Hence:
$5^{2n+1} +3^{n+2} \cdot 2^{n-1} \equiv 5 \cdot 6^n + 90 \cdot 6^n \pmod {19} \equiv 95 \cdot 6^n \pmod {19} \equiv 0 \pmod {19}$
A: $5^{2n+1} = 5 \times 25^n \equiv 5 \times 6^n$ (modulo 19).
Hence we have $5^{2n+1} + 3^{n+2}\times2^{n-1} \equiv 6^{n-1} \times (30 + 27) = 6^{n-1}\times3\times 19$ (modulo 19)
