So the question is as above is shown:
How to prove $8^{2^n} - 5^{2^n}$ is divisible by $13$?
$n=1: 8^2 - 5^2 = 39$ is a multiple of $13$.
I.H.: Suppose $8^{2^n} - 5^{2^n}$ is divisible by $13$ is true $\forall n \in \mathbb{N}\setminus\{0\}$.
I got stuck on this $n= m + 1$ case.
$8^{2^{m+1}} - 5^{2^{m+1}}= 8^{2^m\cdot 2}- 5^{2^m\cdot 2}$
Can somebody please help me?
On
Because $$8^{2^n}-5^{2^n}=64^{2^{n-1}}-25^{2^{n-1}}=(64-25)\left(64^{2^{n-1}-1}+...+25^{2^{n-1}-1}\right)$$ is divisible by $39$ and $39$ is divisible by $13$.
On
For $n>1$ $${(8^2)}^{2^{n-1}}-{(5^2)}^{2^{n-1}}=64^{2^{n-1}}-25^{2^{n-1}}\equiv(-1)^{2^{n-1}}-(-1)^{2^{n-1}}\equiv0~~~\text{mod}~13$$ case $n=1$ is trivial.
On
You could prove by induction that $f(n)=8^{2^n}\equiv1\bmod{13}$ holds for $n\ge3$. Indeed, for $n=2$ we have $f(2)=64\equiv-1\bmod{13}$. Since $f(n+1)\equiv f^2(n)\bmod{13}$, the claim follows.
Analogously, you can prove that $g(n)=5^{2^n}\equiv1\bmod{13}$ for $n\ge3$.
Combining these two observations proves your statement for $n\ge3$. You may easily check the remaining two cases $n=1$ and $n=2$ by hand.
On
More generally, $8^{m} - 5^{m}$ is divisible by $13$ when $m$ is even.
Indeed, $8^{m} - 5^{m} = (13-5)^m-5^m = 13a+5^m-5^m=13a$ by the binomial theorem.
Here is a proof by induction:
$8^{m} - 5^{m}=13a$
$8^{2} - 5^{2}=13b$
$8^{m+2} - 5^{m+2} = 8^m 8^2 - 5^m 5^2 = (13a+5^m)8^2 - 5^m 5^2 = 13c + 5^m 8^2 - 5^m 5^2 = 13c +5^m(8^2 - 5^2) = 13c + 5^m 13b = 13d$
On
Consider the product $$(8-5)(8+5)(8^2+5^2)(8^{2^2}+5^{2^2}) \dots(8^{2^{n-1}}+5^{2^{n-1}})$$which is a form of "telescoping" product. The second factor is equal to $13$. This is equivalent to some other observations people have made, of course, but can be a useful way of looking at things from a different angle.
On
To complete the proof with the following identity $ A^2 - B^2 = (A + B) (A-B) $. I get $\begin{align}\\ \underline {\text{n= m+1:}} \\ 8^{2^n} -5^{2^n} & = 8^{2^{m+1}} -5^{2^{m+1}} \\ & = (8^{2^m} + 5^{2^m})(8^{2^m} -5^{2^m})\\ & = (8^{2^m} + 5^{2^m})\cdot \text{some multiple of 13} \end{align}$
Thus concluding that the entire expression is divisible by 13.
$\bmod 13\!:\,\ 8\equiv -5\,\overset{(\ \ )^{\Large 2}}\Longrightarrow\, 8^{\large 2}\!\equiv 5^{\large 2}\overset{(\ \ )^{\Large N}\!}\Longrightarrow\, 8^{\large 2N}\!\equiv 5^{\large 2N}\,$ by the $ $ Congruence Power Rule.
Remark $ $ Replying to comments, below we show how the inductive proof of the linked Power Rule can be expressed without knowledge of congruences, using analogous divisibility rules.
$\begin{align}{\bf Divisibility\ Product\ Rule}\ \ \ \ &m\mid \ a\ -\ b\qquad {\rm i.e.}\quad \ \, a\:\equiv\: b\\ &m\mid \ \ A\: -\: B\qquad\qquad \ A\equiv\, B\\ \Rightarrow\ \ &\color{}{m\mid aA - bB}\quad \Rightarrow\quad aA\equiv bB\!\pmod{\!m}\\[.2em] {\bf Proof}\,\ \ m\mid (\color{#0a0}{a\!-\!b})A + b(\color{#0a0}{A\!-\!B}) &\,=\, aA-bB\ \ \text{by $\,m\,$ divides $\rm\color{#0a0}{green}$ terms by hypothesis.}\end{align}$
$\begin{align}{\bf Divisibility\ Power\ Rule}\qquad &m\mid a\ -\ b\qquad {\rm i.e.}\qquad a\equiv b\\ \Rightarrow\ \ & m\mid a^n-b^n\quad\ \Rightarrow\quad\,\ \ a^n\!\equiv b^n\pmod{\!m} \end{align}$
Proof $\ $ The base case $\,n=0\,$ is $\,m\mid 1-1\,$ so true, and the inductive step follows by applying the Product Rule, namely $\ m\mid a- b,\,a^n- b^n \Rightarrow\, m\mid a^{n+1}-b^{n+1}.\,$
Your exercise follows from the specialization $\,a = 8^2,\ b = 5^2,\ m = 13\, $ in the above Power Rule. More explicitly, note that we have $\,\color{#c00}{13}\mid 8^2-5^2 = (\color{#c00}{8\!+\!5})(8\!-\!5),\,$ so powering that yields
$\begin{align}{\bf Divisibility\ Power\ Rule}_{\,8,5}\quad &13\mid 8^2 - 5^2\qquad {\rm i.e.}\qquad 8^2\equiv\, 5^2\\ \Rightarrow\ \ & 13\mid 8^{\large 2n}\!-\!5^{\large2n}\quad\ \Rightarrow\quad\,\ \ 8^{\large 2n}\!\!\equiv 5^{\large 2n}\!\!\!\pmod{\!13} \end{align}$
Thus it holds true for all even exponents $2n,\,$ which includes your expoents $2^n,\ n\ge 1.$