prove that for every integer,$ n$, greater than $1$,$ (3^{2n+1}) + (5^{2n-1})$ is divisible by $16$

Question

Could someone please help me out with this proof?

Prove that for every integer $n≥1$, $3^{2n+1} + 5^{2n-1}$, is divisible by $16$.

I get to a point where I have...

$$3^{2k+1} \cdot 3^2 + 5^{2k-1} \cdot 5^2 $$

Thanks!

Answer 1

The order of $3$ and $5$ in $(\mathbb{Z}/16\mathbb{Z})^*$ is four, hence you need to check the claim only for two cases: $n=1$ and $n=2$. For the remaining cases, just use the fact that: $$3^{2(n+2)+1}\equiv 3^{2n+1}\pmod{16},\qquad 5^{2(n+2)-1}\equiv 5^{2n-1}\pmod{16}.$$

Answer 2

Do it by induction: Base case $n=1$: $3^{3}+5=32$.

Now, $$\begin{eqnarray*}3^{2(n+1)+1}+5^{2(n+1)-1}&=&3^2\cdot3^{2n+1}+5^2\cdot 5^{2n-1}\\&=&3^2\cdot3^{2n+1}+3^2\cdot5^{2n-1}+16\cdot 5^{2n-1}\\&=&3^2\cdot (3^{2n+1}+5^{2n-1})+16\cdot 5^{2n-1},\end{eqnarray*}$$ which is divisible by $16$, since the second term is clearly divisible by $16$, while the first term is divisible by $16$ by induction hypothesis.

Answer 3

Let us first just change shift the index by 1 to make calculations easier. Then we need to show that $$3^{2(n+1)+1}+5^{2(n+1)-1}\equiv0 \pmod{16}\quad \forall n\ge0$$ Now, $25\equiv9\pmod{16}$ and $3^{2(n+1)+1}+5^{2(n+1)-1}=9^{n}\cdot27+25^{n}\cdot5$ so $$\begin{align*}&3^{2(n+1)+1}+5^{2(n+1)-1}\pmod{16} \\ \equiv &9^{n}\cdot27+25^{n}\cdot5\pmod{16}\\ \equiv &9^{n}\cdot27+9^{n}\cdot5\pmod{16} \\ \equiv &9^n\cdot32\pmod{16} \\ \equiv &0\pmod{16} \quad \blacksquare\end{align*}$$

Answer 4

I generalized this here: When is there an $m$ that divides $u^{an+b}+v^{cn+d}$ for all $n$

I asked: Find conditions on positive integers $u, a, v, c$ and non-negative integers $b, d$, such that there exists an $m$ which divides $f(n) = u^{an+b}+v^{cn+d}$ for all $n$. Determine $m$ in terms of $u, a, b, v, c, d$.

One conclusion was that if $(u^a-v^c)|(u^b+v^d)$, it divides $f(n)$ for all $n$.

In this case, putting $n+1$ for $n$ (so $d$ is not negative), $(u, a, v, c, b, d) = (3, 2, 5, 2, 3, 1) $, so $u^a-v^c =3^2-5^2 =-16 $ and $u^b+v^d =3^3+5^1 =27+5 =32 $. Since $-16$ divides $32$, $16$ divide all terms.