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

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!

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}.$$

• very nice solution +1. – voldemort Sep 7 '14 at 1:07

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.

• @JackD'Aurizio: right- let me edit it.. thanks. – voldemort Sep 7 '14 at 1:05
• I improved formatting, hope you don't mind. (+1) – Jack D'Aurizio Sep 7 '14 at 1:15

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*}

• Or, before shifting: $3^{2n+1}+5^{2n-1} = 9^n\cdot 3 + 25^n\cdot5^{-1} \equiv 9^n\cdot 3+9^n\cdot(-3)=0\pmod{16}$. – Greg Martin Sep 7 '14 at 2:06
• @GregMartin Indeed! I shall make the edit once I come back from my trip. – E.O. Sep 7 '14 at 2:27

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.

• This is unlikely to be at all helpful to the OP. – Greg Martin Sep 7 '14 at 6:57
• Maybe not, but it is likely to help those who want to solve this type of problem. Besides, it is a solution. I can understand downvoting an incorrect solution, but downvoting a correct solution? – marty cohen Sep 7 '14 at 16:46