# Prove that 3^(2n+1) + 4^(2n+1)is divided by 7

Anzas
prove that 3^(2n+1) + 4^(2n+1)
is divided by 7 for every natural n

Homework Helper
What have you done so far?

snoble
this isn't that hard. It is just induction as you suspect. The only fact you need to know is that $$c_1n + c_2m \equiv b_1n + b_2m\, (mod\, k)$$ if $$c_1\equiv b_1,\,c_2\equiv b_2\,(mod\, k)$$.

So just write down your sequence $$a_n = 3^{2n+1}+4^{2n+1}$$. When $$a_n$$ is in that form can you write down $$a_{n+1}$$ without out modifying the exponent.

Hope those hints help.
Steven

Anzas
well assuming that 3^(2n+1) + 4^(2n+1) is divisible by 7
im writing down what needs to be proven for n=n+1

3^(2n+3) + 4^(2n+3) / 7 = some integer = Z

9*3^(2n+1)+16*4^(2n+1) / 7 = Z

3^(2n+1)+4^(2n+1) / 7 + 8*3^(2n+1)+15*4^(2n+1) / 7 = Z

the first term is divisible because of the induction assumption so that leaves me with
8*3^(2n+1)+15*4^(2n+1) / 7

here im stuck i can't find a way to show that this term is divisible by 7
i tried proving that with another induction but that led me no where.
i also tried transforming 8*3^(2n+1)+15*4^(2n+1) / 7 to
7*3^(2n+1)+7*4^(2n+1) / 7 + 3^(2n+1)+8*4^(2n+1) / 7

3^(2n+1)+4^(2n+1) + 3^(2n+1)+8*4^(2n+1) / 7
and that leaves me with the term 3^(2n+1)+8*4^(2n+1) / 7
that does not help me i can't find a way to show that its divisible by 7
any help/tips would be appreciated

sorry for not using latex by the way it would just take me too much time to type all this in latex

snoble
Oh you're so close!

(3^(2n+1)+4^(2n+1)) / 7 + (8*3^(2n+1)+15*4^(2n+1)) / 7
= (3^(2n+1)+4^(2n+1)) / 7 + (3^(2n+1)+4^(2n+1)) / 7 + (7*3^(2n+1)+14*4^(2n+1)) / 7

You just needed to do your trick one more time over

Hope that helps
Steven

Anzas
of course! i can't believe i didn't notice this thank you very much!

Algebracus
We can easily prove it without induction:

$$a_n = 3^{2n+1}+4^{2n+1}\equiv 3^{2n+1} + (-3)^{2n+1} \equiv 3^{2n+1}\cdot(1 + (-1)^{2n+1}) \equiv 0 (mod 7)$$.