# Thread: Prove 16^m + 10m -1 is always divisible by 25

1. ## Prove 16^m + 10m -1 is always divisible by 25

How can I prove that $16^m + 10m -1$ is always divisible by 25 when $m$ is a whole number greater than zero.

2. Originally Posted by jeremy5561
How can I prove that $16^m + 10m -1$ is always divisible by 25 when $m$ is a whole number greater than zero.
sounds like a proof by induction ... show true for m = 1, assume true for m, prove true for (m+1)

3. 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 . . .

$\text{Prove that: }\,16^m + 10m -1 \,\text{ is divisible by 25 for any positive integer }m.$

$\text{Verify }S(1)\!:\;16^1 + 10(1) - 1 \:=\:25\;\hdots\;\text{True!}$

$\text{Assume }S(k)\!:\;16^k + 10k - 1 \:=\:25a\,\text{ for some integer }a.$

$\text{Add }(15\!\cdot\!16^k + 10)\text{ to both sides:}$

. . $16^k + {\bf15\!\cdot\!16^k} + 10k + {\bf10} - 1 \;=\;25a + {\bf15\!\cdot\!16^k} + {\bf10}$

. . . $(1 + 15)\!\cdot\!16^k + 10(k+1) - 1 \;=\;25a + 15\!\cdot\!16^k + 10$

. . . . . . . $\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 $15\!\cdot\!16^k + 10$ is a multiple of 25.
. . That is, that $3\!\cdot\!16^k + 2$ is a multiple of 5.

$3\!\cdot\!16^k + 2 \;=\;3(4^2)^k + 2$

. . . . . . . . $=\;3(4)^{2k} + 2$

. . . . . . . . $=\;3(5-1)^{2k} + 2$

. . . . . . . . $=\;3\bigg[5^{2k} - {2k\choose2k-1}5^{2k-1} + \hdots + {2k\choose2}5^2 - {2k\choose1}5 + 1\bigg] + 2$

. . . . . . . . $=\;3\bigg[5^{2k} - {2k\choose2k-1}5^{2k-1} + \hdots + {2k\choose2}5^2 - {2k\choose1}5\bigg] + 3 + 2$

. . . . . . . . $=\;3\bigg[5^{2k} - {2k\choose2k-1}5^{2k-1} + \hdots + {2k\choose2}5^2 - {2k\choose1}5\bigg] + 5$

. . . . . . . . $=\;5\,\bigg[3\bigg(5^{2k-1} - {2k\choose2k-1}5^{2k-2} + \hdots + {2k\choose2}5 - {2k\choose1}\bigg) + 1\bigg]$

. . $\text{Q. E. D.}$

But there must be a better way!
.

4. My teacher hinted towards the binomial theorem. Don't know if that will help. He didn't say much else.

5. Maybe try writing it as
$(15+1)^m+10m-1$
and then expand using the binomial theorem.

6. If you know any modern algebra (modular arithmetic), you only really need check the cases $m=0,1,2,3,4$, since $16^5\equiv1\,(\mod\,25)$. You could generalize each of those cases to when $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.