How can I prove that $\displaystyle 16^m + 10m -1$ is always divisible by 25 when $\displaystyle m$ is a whole number greater than zero.
Hello, jeremy5561!
skeeter is right . . . An inductive proof is in order.
Even then, I had difficulty with the inductive step.
Perhaps someone has a better method . . .
$\displaystyle \text{Prove that: }\,16^m + 10m -1 \,\text{ is divisible by 25 for any positive integer }m.$
$\displaystyle \text{Verify }S(1)\!:\;16^1 + 10(1) - 1 \:=\:25\;\hdots\;\text{True!}$
$\displaystyle \text{Assume }S(k)\!:\;16^k + 10k - 1 \:=\:25a\,\text{ for some integer }a.$
$\displaystyle \text{Add }(15\!\cdot\!16^k + 10)\text{ to both sides:}$
. . $\displaystyle 16^k + {\bf15\!\cdot\!16^k} + 10k + {\bf10} - 1 \;=\;25a + {\bf15\!\cdot\!16^k} + {\bf10}$
. . .$\displaystyle (1 + 15)\!\cdot\!16^k + 10(k+1) - 1 \;=\;25a + 15\!\cdot\!16^k + 10$
. . . . . . . $\displaystyle \underbrace{16^{k+1} + 10(k+1) - 1}_{\text{Left side of }S(k+1)} \;=\;25a + 15\!\cdot\!16^k + 10$
And we must show that $\displaystyle 15\!\cdot\!16^k + 10$ is a multiple of 25.
. . That is, that $\displaystyle 3\!\cdot\!16^k + 2$ is a multiple of 5.
$\displaystyle 3\!\cdot\!16^k + 2 \;=\;3(4^2)^k + 2$
. . . . . . . .$\displaystyle =\;3(4)^{2k} + 2$
. . . . . . . .$\displaystyle =\;3(5-1)^{2k} + 2$
. . . . . . . .$\displaystyle =\;3\bigg[5^{2k} - {2k\choose2k-1}5^{2k-1} + \hdots + {2k\choose2}5^2 - {2k\choose1}5 + 1\bigg] + 2$
. . . . . . . .$\displaystyle =\;3\bigg[5^{2k} - {2k\choose2k-1}5^{2k-1} + \hdots + {2k\choose2}5^2 - {2k\choose1}5\bigg] + 3 + 2 $
. . . . . . . .$\displaystyle =\;3\bigg[5^{2k} - {2k\choose2k-1}5^{2k-1} + \hdots + {2k\choose2}5^2 - {2k\choose1}5\bigg] + 5 $
. . . . . . . .$\displaystyle =\;5\,\bigg[3\bigg(5^{2k-1} - {2k\choose2k-1}5^{2k-2} + \hdots + {2k\choose2}5 - {2k\choose1}\bigg) + 1\bigg] $
. . $\displaystyle \text{Q. E. D.}$
But there must be a better way!
.
If you know any modern algebra (modular arithmetic), you only really need check the cases $\displaystyle m=0,1,2,3,4$, since $\displaystyle 16^5\equiv1\,(\mod\,25)$. You could generalize each of those cases to when $\displaystyle m=5q+r,r=0,1,2,3,4$.
I wouldn't recommend this over the induction, if the induction didn't look so messy.