For $n \in \mathbb{N}$, show that $4^n + 10 \times 9^{2n-2}$ is divisible by 7

Question

For $n \in \mathbb{N}$, show that $4^n + 10 \times 9^{2n-2}$ is divisible by 7.

I'm not sure how to do this proof so any help would be appreciated.

Answer 1

Induction can certainly be used, but a more direct method will also work as follows - (The trick here is to get to 7 as far as possible, so 9 = 7+2, etc)

$4^n + 10 \times 9^{2n-2}$

= $4^n + 3 \times (7 + 2)^{2n-2}$ (mod 7)

= $4^n + 3 \times 2^{2n-2}$ (mod 7)

= $4^n + 3 \times 4^{n-1}$ (mod 7)

= $4^{n-1}(4 + 3)$ (mod 7)

= $4^{n-1}(0)$ (mod 7)

= $0$ (mod 7)

Edit:- In fact, because the expression is even, $14$ divides it for all $n$

Answer 2

If $n=1$, then $$ 4^{n} + 10\cdot 9^{2n-2} = 4+10 = 14, $$ divisible by $7$; if $n \geq 1$ is an integer such that $4^{n} + 10\cdot 9^{2n-2} = 7k$ for some integer $k \geq 1$, then $$ 4^{n+1} + 10\cdot 9^{2(n+1) - 2} = 4\cdot 4^{n} + 10\cdot 9^{2n} = 4(4^{n} + 10\cdot 9^{2n-2}) = 28k, $$ divisible by $7$.

Answer 3

We have $$9^{2n-2} = (7+2)^{2n-2} = \sum_{k=0}^{2n-2} \dbinom{2n-2}k 7^k2^{2n-2-k} = 2^{2n-2} + 7M$$ Hence, we have \begin{align} 4^n+10 \cdot 9^{2n-2} & = 4^n + 10 \cdot (2^{2n-2}+7M) = 4^n+10\cdot 4^{n-1} + 70M = 4^{n-1}(4+10)+70M\\ & = 14(5M+4^{n-1}) \end{align} Hence, in fact we have that $14$ divides $4^n+10 \cdot 9^{2n-2}$ for all $n \in \mathbb{Z}^+$

Answer 4

$\underline{\text{Proof by induction:}}$

First, show that this is true for $n=1$:

$4^1+10\cdot9^{2-2}=14$

Second, assume that this is true for $n$:

$4^n+10\cdot9^{2n-2}=7k$

Third, prove that this is true for $n+1$:

$4^{n+1}+10\cdot9^{2(n+1)-2}=$

$4^{n+1}+10\cdot9^{2n+2-2}=$

$4^{n+1}+10\cdot9^2\cdot9^{2n-2}=$

$4\cdot4^n+810\cdot9^{2n-2}=$

$4\cdot(\color\red{4^n+10\cdot9^{2n-2}})+770\cdot9^{2n-2}=$

$4\cdot\color\red{7k}+770\cdot9^{2n-2}=$

$28k+770\cdot9^{2n-2}=$

$7\cdot(4k+110\cdot9^{2n-2})$

Please note that the assumption is used only in the part marked red.

Answer 5

$9\equiv2\pmod7\implies9^{2m}\equiv2^{2m}\equiv4^m$

$$4^{m+1}+10\cdot9^{2m}\equiv4^{m+1}+10\cdot4^m\equiv4^m(4+10)\equiv0\pmod{14}$$