Divisibility by 7 Proof by Induction

$b-a=4^{2\cdot2^k}-4^{2^k}+2^{2\cdot2^k}-2^{2^k}$

$=4^{2^k}(4^{2^k}-1)+2^{2^k}(2^{2^k}-1)$

$=4^{2^k}(2^{2^k}-1)(2^{2^k}+1)+2^{2^k}(2^{2^k}-1)$

$=(2^{2^k}-1)(8^{2^k}+4^{2^k}+2^{2^k})$

$=(2^{2^k}-1)2^{2^k}\color{blue}{(4^{2^k}+2^{2^k}+1)}$

Divisibility by $7$ is congruence to zero modulo $7.$ So we might get some insights by looking at the numbers' congruences mod $7$.

Note that $x^{2^{k+1}} = x^{2^k\cdot 2} = \left(x^{2^k}\right)^2.$ That is, every time we add $1$ to the exponent $k$ in $2^{2^k}$ or $4^{2^k}$, we square the number.

So let's try applying these two ideas: do the arithmetic modulo $7$; and try the first few values of $n$ and see what happens.

So what happens is \begin{align} 2^2 \equiv 4 \pmod7,\\ 4^2 \equiv 2 \pmod7.\\ \end{align}

That is, \begin{align} \text{for } n &= 1, & 4^{2^1} + 2^{2^1} + 1 = 4^2 + 2^2 + 1 &\equiv 2 + 4 + 1 \pmod7,\\ \text{for } n &= 2, & 4^{2^2} + 2^{2^2} + 1 \equiv 2^2 + 4^2 + 1 &\equiv 4 + 2 + 1 \pmod7,\\ \text{for } n &= 3, & 4^{2^3} + 2^{2^3} + 1 \equiv 4^2 + 2^2 + 1 &\equiv 2 + 4 + 1 \pmod7,\\ \end{align} and so forth.

You should now know the congruence classes of $4^{2^n}$ and $2^{2^n}$ for every $n$ and be able to prove the obvious pattern of congruences for alternating odd and even $n$ by induction. This is just a little less elegant that some of the other proofs in that you may find it necessary to have two cases in the inductive step, one for odd $k$ and one for even $k.$

$ b - a = 4^{2^{k+1}} + 2^{2^{k+1}} - 4^{2^k}-2^{2^k}$

An intermediate step: notice $4=2^2$, so we have that $b-a = 2^{2^{k+2}} + 2^{2^{k+1}} - 2^{2^{k+1}}-2^{2^k} = 2^{2^{k+2}} -2^{2^k} $

Notice that each term is divisible by $2^{2^k}$, and $7$ does not divide $2^{2^k}$.

Now $\frac{b-a}{2^{2^k}} = 2^{2^{k+2} - 2^k} -2^{2^k - 2^k} = 2^{3 \times 2^k} - 2^0 = 8^{2^k} -1$

Now it is more of a bonus fact that $8^m -1$ is always divisible by $7$.