Prove that 9 divides $7\cdot5^{2n}+2^{4n+1}$

Question

We have to prove that the following statement is true for all non zero natural numbers: $$9|7\cdot5^{2n}+2^{4n+1}$$

Answer 1

with congruence:

$7\cdot5^{2n}+2^{4n+1}\equiv$

$(-2)\cdot(-4)^{2n} + 2^{4n}\cdot 2\equiv $

$-2\cdot 16^n + 16^n \cdot 2 \equiv 0\pmod 9$.

Oh... I didn't actually expect it to end so soon.

.... By induction:

You can't go wrong with induction.

$7*5^2 + 2^5 = 7*25+ 32= 207=9*23$.

Okay... that was the base case.

If $7*5^{2k} + 2^{4k+1}$ is divisible by $9$ then

$7*5^{2(k+1)} + 2^{4(k+1)+1}=$

$7*5^{2k}\times 25 + 2^{4k+1}\times 16=$

$7*5^{2k}\times (16+9) + 2^{4k+1}\times 16=$

$16(7*5^{2k} + 2^{4k+1}) + 9(7*5^{2k})$.

And $9$ divides $7*5^{2k} + 2^{4k+1}$ and $9$ divides $9(7*5^{2k})$ so $9$ divides the sum which is $7*5^{2(k+1)} + 2^{4(k+1)+1}$

So that's our induction step.

Answer 2

$$=7(5^{2n}-2^{4n})+9\cdot2^{4n}$$

Now for integer $n,$ $$5^{2n}-2^{4n}=(5^2)^n-(2^4)^n=25^n-16^n$$

Use Why is $a^n - b^n$ divisible by $a-b$?

Answer 3

Hint:

Modulo $9$, $5\equiv-4$, so $7\cdot5^{2n}+2^{4n+1}\equiv 7\cdot4^{2n}+2\cdot4^{2n}$.