An expression is divible by 4 but not 8.

Question

Let $n\in\mathbb{N}$.

Show that $4\mid(3^{2n+1} + 5^{2n})$ and $8\nmid(3^{2n+1} + 5^{2n})$

$(2m+1)^n = (2m+1)_1(2m+1)_2...(2m+1)_n$.

Here I'm trying to show that an odd number raised to any integer is still odd; I was then going to use it in the equation system above to show that the expression would always turn out to be even.

I know that I need to show that the expression is never going to have more than two $2$'s as factors. I'm a little puzzled as to how. I think I'm doing it wrong in the last step aswell, maybe making it a little more difficult than it has to be.

Probable solution?

$\begin{cases} 3\cdot 3 &= 2\cdot 4 + 1 \\ 5 &= 1\cdot4 + 1 \end{cases} \iff \begin{cases} 3^{2n+1} &\equiv 1^{2n+1} &\bmod 4 \\ 5^{2n} &\equiv 1^{2n} &\bmod 4 \end{cases}$

$\implies 3^{2n+1} + 5^{2n} \equiv 1^{2n+1} + 1^{2n} = 1 + 1 \equiv 2 \bmod 4$

Which leads to the wrong proposition. And I know the proposition is correct. What did I do wrong?

Answer 1

Note that $$3^{2n+1}+5^{2n}\equiv (\color{red}{-1})^{2n+1}+1^{2n}=-1+1=0\pmod 4$$ and that $$3^{2n+1}+5^{2n}=3\cdot 9^n+25^n\equiv 3\cdot 1^n+1^n\equiv 3+1\equiv 4\not\equiv 0\pmod8$$

Answer 2

Your idea is correct. There is just one little mistake: You noticed $3 \cdot 3 \equiv 1 \bmod 4$. This does not imply $3^{2n+1} \equiv 1^{2n+1} \bmod 4$, but it tells you that $$3^{2n+1} = 3 \cdot (3^2)^n \equiv 3 \cdot 1 = 3 \mod{4}$$ which is exactly what you want.

Now for $8$, try to do a similar thing. Hint: $3^2 \equiv 5^2 \equiv 1 \bmod 8$.