# Prove 5|(3^(3n+1)+2^(n+1)) for every positive integer n.

1. Mar 18, 2014

### Tsunoyukami

"Prove $5|(3^{3n+1}+2^{n+1})$ for every positive integer $n$." (Exercise 11.8 from Mathematical Proofs: A Transition to Advanced Mathematics 3rd edition by Chartrand, Polimeni & Zhang; pg. 282)

I'm having difficulty solving this exercise. My first thought was to use induction but I get stuck with an expression that I can't seem to manipulate into the required form. The next thing I tried was considering cases (when $n$ is even and when $n$ is odd) but once again I get stuck.

Can anyone suggest another method of proof?

I feel that induction should work out for me despite my difficulties. As such, I will explain what I've done so far. If you would like to see work I describe but do not include below let me know and I'll include it.

First I showed that this expression holds for the case $n=1$. I assumed this holds for some arbitrary positive integer $k$. Now I wish to show that $5|(3^{3(k+1)+1}+2^{(k+1)+1})$.

From here I tried working with the expression $3^{3(k+1)+1}+2^{(k+1)+1}$:

$3^{3(k+1)+1}+2^{(k+1)+1}=3^{3k+3+1}+2^{k+1+1}=3^{3k+4}+2^{k+2}=3^{3k} \cdot 3^4 + 2^{k} \cdot 2^{2}=81\cdot3^{3k}+4\cdot2^{k}$

This is where I get stuck - I don't know how to massage this equation to show that 5 divides it.

2. Mar 18, 2014

### Dick

Write that as $3^{3(k+1)+1}+2^{(k+1)+1}=27*3^{3k+1}+2^{k+1}$. Note 27=25+2.

3. Mar 18, 2014

### Tsunoyukami

Thanks so much for the hint!

So we can write:

$3^{3(k+1)+1}+2^{(k+1)+1}$
$= 27 \cdot 3^{3k+1}+2\cdot 2^{k+1}$
$=(25+2)\cdot 3^{3k+1}+2 \cdot 2^{k+1}$
$=25 \cdot 3^{3k+1} + 2 \cdot 3^{3k+1} + 2\cdot 2^{k+1}$
$= 25 \cdot 3^{3k+1} + 2 \cdot (3^{3k+1} + 2^{k+1})$

By assumption we know that $5|(3^{3k+1} + 2^{k+1})$ so we can write $(3^{3k+1} + 2^{k+1})=5x$ for some integer x.

Then we have
$= 25 \cdot 3^{3k+1} + 2 \cdot (3^{3k+1} + 2^{k+1})$
$=5(5\cdot3^{3k+1})+5\cdot2x$
$=5(5\cdot3^{3k+1}+2x)$

Since $5\cdot3^{3k+1}+2x$ is an integer, we conclude that $5|3^{3(k+1)+1}+2^{(k+1)+1}$.

Last edited: Mar 18, 2014
4. Mar 18, 2014

### Dick

Right. You definitely want to keep $3^{3k+1} + 2^{k+1}$ in the answer somehow because you know it's divisible by 5. And splitting the factor up becomes pretty obvious once you've seen the trick.