Prove $5 \mid 2^{n+1} + 3^{3n+1}$

I tried induction, so I assume the hypothesis and attempt to show $5 \mid 2^{n+2} +3^{3n + 4}$ but this doesn't help. I tried breaking it down into prime factorizations, but I do not see it.

• Please reconcile the title & the body – lab bhattacharjee Sep 21 '13 at 15:51

$2^{n+1}+3^{3n+1}=2\cdot2^n+3\cdot(3^3)^n$

$\equiv2\cdot2^n+3\cdot(2)^n\pmod5$ as $3^3=27\equiv2\pmod5$

$\equiv2^n(2+3)\pmod5\equiv0$

• Great answer, I didn't know I was supposed to use modulo arithmetic. – Don Larynx Sep 21 '13 at 15:55
• It's $3^{3n+4}$ instead of $3^{n+4}$ – Stefan4024 Sep 21 '13 at 16:02
• @Stefan4024, have you notified the difference between the title & the body of the question? – lab bhattacharjee Sep 21 '13 at 16:10
• As far as I understand he tried to use unduction to solve the question, assuming that $5|2^{n+1} + 3^{3n+1}$ holds, then he tried to prove that this holds too: $5|2^{(n+1) + 1} + 3^{3(n+1) + 1} = 2^{n+2} + 3^{3n + 4}$ – Stefan4024 Sep 21 '13 at 16:37
• @Stefan4024, good observation. – lab bhattacharjee Sep 21 '13 at 16:40

Hints:

$$2^{n+1}+3^{3n+1}=2(2^n+3^{3n-2})+25\cdot 3^{2n-1}$$

and use induction on $\;n\;$ ...

Hint: 1) $27 = 2 \mod 5$ and

2) $3=-2 \mod 5$

Can u do it now?

Hint: \begin{align}2^{n+2}+3^{3n+4}&=3^3\left(3^{3n+1}+2^{n+1}\right)+\left(2^{n+2}-3^3(2^{n+1})\right)\\&=5k+2^{n+1}(2-3^3)\\&=5k+5\ell\end{align}