$13\mid4^{2n+1}+3^{n+2}$

Question

How can I prove that $4^{2n+1}+3^{n+2}$ is always divisible by 13?

Answer 1

$$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

Answer 2

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$.

Answer 3

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

Answer 4

By induction: the base case $n=0$ is obvious. Assume true for $n=k$, so all that remains to show is for $n=k+1$.

Since we know the claim is true for $n=k$:

$$A_k : = 4^{2k+1}+3^{k+2}$$

is divisible by 13. We proceed by showing that $A_{k+1} - 3 A_k$ is divisible by 13, from which the claim follows: $$= 4^2 \cdot4^{2k+1} + 3\cdot3^{k+2} - 3(4^{2k+1} + 3^{k+2}) = 4^{2k+1}\cdot 13$$

So we are done.

Answer 5

let's using mod function $$ \left(4^{2n+1}+3^{n+2} \right)\text{ mod }13=\left((4-13)^{2n+1}+3^{n+2} \right)\text{ mod }13=\left(-3^{4n+2}+3^{n+2} \right)\text{ mod }13 $$ $$ \because \text{ }3^3\text{ mod }13=1 \text{ }\therefore\text{ }3^n\text{ mod }13=3^{n\text{ mod }3} $$ $$ \to \left(-3^{4n+2}+3^{n+2} \right)\text{ mod }13 =\left(-3^{n+2}+3^{n+2} \right)\text{ mod }13=0$$ $$ \therefore 4^{2n+1}+3^{n+2} \text{ is divisible by }13$$