$13\mid4^{2n+1}+3^{n+2}$ How can I prove that $4^{2n+1}+3^{n+2}$ is always divisible by 13?
 A: $$4^{2n+1}+3^{n+2}=16^n\cdot 4+3^n\cdot 9\\16^n\cdot4+3^n\cdot 9\equiv3^n\cdot4+3^n\cdot 9\pmod {13}\\3^n(4+9)\equiv3^n\cdot13\equiv0\pmod{13}$$
This can also be solved with induction,for $n=0$
$$4+3^2=13$$
Assume it holds for $n=k$
$$4^{2k+1}+3^{k+2}$$
Prove it holds for $n=k+1$
$$4^{2k+3}+3^{k+3}=16\cdot4^{2k+1}+3\cdot3^{k+2}=16\cdot4^{2k+1}+16\cdot3^{k+2}-13\cdot3^{k+2}=16(4^{2k+1}+3^{k+2})-13\cdot3^{k+2}$$
by the inductive hypothesis $4^{2k+1}+3^{k+2}$ is divisible by $13$ because of that the whole expression is
A: You can use congruence:
$$
4^{2n+1}+3^{n+2}\equiv 4(16^n)+9(3^n) \equiv 4(16^n)+(13-4)(3^n) \equiv 4(16^n-3^n) \equiv 4(3^n-3^n) \equiv 0\ (\text{mod }13).
$$
Also you can prove it directly:
$$
4^{2n+1}+3^{n+2} = 4(16^n-3^n)+(13)(3^n) = 13[4(16^{n-1}+16^{n-2}3+16^{n-3}3^2+\ldots+3^{n-1})+3^n]
$$
which proves that $4^{2n+1}+3^{n+2}$ is dividable by $13$. 
A: Hint $\ $ Specialize $\, a = 3\,$ below. $ $ See this post for an inductive proof and further discussion.
Theorem $\quad a^2\!+a+1\mid a^{n+2}+(a\!+\!1)^{2n+1}\!  =: b$
Proof $\, \ {\rm mod}\,\ a^2\!+a+1\!:\ \color{#0a0}{a(a\!+\!1)\equiv -1}$ and $\,\color{#c00}{a^3\equiv 1}\ $ by $\,0\equiv (a\!-\!1)(a^2\!+a+1) = a^3\!-1,\,$ so
$\qquad\quad\! a^{2n+1}b = a^{3n+3} + (\color{#0c0}{a(a\!+\!1)})^{2n+1} \equiv\, (\color{#c00}{a^3})^{n+1}\!-1\equiv 0$
Thus $\,\ a^{2n+1}b \equiv 0\ $ times $\,a^{n-1}\,$ yields $\ b \equiv (\color{#c00}{a^3})^n b\equiv 0\ \ $ QED 
A: Hint: Try using induction to prove the statement.
