0
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ very nice solution +1. $\endgroup$ – voldemort Sep 7 '14 at 1:07
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @JackD'Aurizio: right- let me edit it.. thanks. $\endgroup$ – voldemort Sep 7 '14 at 1:05
  • 1
    $\begingroup$ I improved formatting, hope you don't mind. (+1) $\endgroup$ – Jack D'Aurizio Sep 7 '14 at 1:15
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Greg Martin Sep 7 '14 at 2:06
  • $\begingroup$ @GregMartin Indeed! I shall make the edit once I come back from my trip. $\endgroup$ – E.O. Sep 7 '14 at 2:27
-1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is unlikely to be at all helpful to the OP. $\endgroup$ – Greg Martin Sep 7 '14 at 6:57
  • $\begingroup$ 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? $\endgroup$ – marty cohen Sep 7 '14 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.