Prove that $5$ divides $3^{3n+1}+2^{n+1}$

Question

Prove that $5$ divides $3^{3n+1}+2^{n+1}$

I tried to prove the result by induction but I couldn't.

The result is true for $n=1$.

Suppose that the result is true for $n$ i.e $3^{3n+1}+2^{n+1}=5k$ for some $k\in \mathbb{N}$. We study the term

$$3^{3n+4}+2^{n+2}=3^{3n+1}3^3+2^{n+1}2$$

I tried to prove that that the difference is a multiple of $5$.

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

Therefore it's enough to prove that $3^{3n+1}\cdot 13+2^n$ is a multiple of $5$. But if I do again this method applied to this "new problem" is get something similar. I think that there exist a different method to do this using induction.

Answer 1

Hint :

$$3^{3n+4}+2^{n+2}=27\times 3^{3n+1}+2\times 2^{n+1}=2\times(3^{3n+1}+2^{n+1})+25\times 3^{3n+1}$$

Answer 2

$$3^{3n+4}+2^{n+2}=3^{3n+1}\cdot 3^{3} +2^{n+1}\cdot 2\\ =(5k-2^{n+1})\cdot 3^{3}+2^{n+1}\cdot 2\\ =2^{n+1}(2-27)+5k\cdot 27=-2^{n+1}\cdot 25+5k\cdot 27\\ =5(-2^{n+1}\cdot 5+27k)$$ which is divisible by $5$.

Answer 3

Your approach works if you just subtract once more: $$ 3^{3n+4} + 2^{n+2} - 2\cdot 5k\\ = 27\cdot 3^{3n+1} + 2\cdot 2^{n+1} - 2(3^{3n+1} + 2^{n+1})\\ = 25\cdot 3^{3n+1} $$ and you're done.

Answer 4

$3 (27^{n})+2 (2^{n}) $ is equal to your value,so $3 (2^{n})+2 (2^{n})=5( 2^{n}) $ has equal remainder (as dividing by 5) with the previous value because 27 has the same remainder ( with respect to 5) as 2. so it is proved.

Answer 5

try this $$3^{3n+1}3^3+2^{n+1}2-3^{3n+1}+2^{n+1}=3^{3n+1}\cdot26+2^{n+1}$$

$$3^{3n+1}\cdot26+2^{n+1}=3^{3n+1}\cdot25+3^{3n+1}+2^{n+1}$$

since $3^{3n+1}+2^{n+1}=5k$

$$3^{3n+1}\cdot25+3^{3n+1}+2^{n+1}=3^{3n+1}\cdot25+5k$$

the difference is divisable by $5$

Answer 6

I don't see why people want to avoid modular arithmetic in solving problems like this. Fermat's little theorem is not required:

Let $f(n) = 3^{3n+1}$ and $g(n) = 2^{n+1}$. We want to prove that $f(n) \equiv -g(n) \;(\mathrm{mod}\;5)$. When $n=0$ this says that $3 \equiv -2\;(\mathrm{mod}\;5)$ which is true. Noting that $f(n+1) = 27f(n) \equiv 2f(n) \;(\mathrm{mod}\;5)$ and $g(n+1) = 2g(n)$, we have that, if $f(n) \equiv -g(n) \;(\mathrm{mod}\;5)$, then also

$$f(n+1) \equiv 2f(n) \equiv -2g(n) \equiv -g(n+1) \;(\mathrm{mod}\;5)$$

and so what we wanted to prove follows by induction.

Answer 7

Or we could just expand and rearrange$$ \begin{align} 3^{3n+1}+2^{n+1} &= 3\cdot27^n + 2\cdot2^n \\ &= 3\cdot(25+2)^n + 2\cdot2^n \\ &= 3\left(5k+2^n \right) + 2\cdot 2^n \tag{Using Binomial Theorem}\\ &= 5\cdot k'+3\cdot2^n+2\cdot2^n \\ &= 5\cdot k'+5\cdot 2^n \\ \end{align} $$ Hence proved