# How to prove $8^{2^n} - 5^{2^n}$ is divisible by $13$ where $n\in\mathbb{N}-\{0\}$ with induction?

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}$

• Hint: Your last expression is of the form $A^2-B^2$ with $A=8^{2^m}$ and $B=5^{2^m}$ – Kelenner Sep 11 '17 at 13:33
• Oh, of course. Thx for the insight. – Anonymous196 Sep 11 '17 at 13:40

$\bmod 13\!:\,\ 8\equiv -5\,\Rightarrow\, 8^{\large 2}\!\equiv 5^{\large 2}\color{}{\Rightarrow}\, 8^{\large 2N}\!\equiv 5^{\large 2N}\,$ by the  Congruence Power Rule.

Remark  Replying to comments, below I 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}\qquad &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.$

• The Power Rule has a simple inductive proof - see the lined post. – Bill Dubuque Sep 11 '17 at 14:12
• Yeah I've already remarked that with modular arithmetic. I wanted it proof the above expression without using this method. Thanks for the tip though. I should have said that earlier – Anonymous196 Sep 11 '17 at 14:15
• @AnonymousI Then you can use $\, a-b\mid a^n-b^n\,$ for $\,a=8^2,\, b = 5^2,\,$ which is a special case of the Polynomial Factor Theorem $\, x-y\mid f(x)-f(y),\,$ which has a very simple inductive proof using the Polynomial Division Algorithm (follow the link). – Bill Dubuque Sep 11 '17 at 14:23
• With my previous remark I meant that I only came up with 8 is congruent with -5( mod 13) and I knew that if you took the power of the congruent those were the same mod 13. And then I stopped without realizing what you wrote at last. It was helpful. – Anonymous196 Sep 11 '17 at 14:34
• @AnonymousI Generally $\ a\equiv b\,\Rightarrow\, f(a)\equiv f(b)\,$ for any polynomial $\,f(x)\,$ with integer coefficients (above is special case $\,f(x) =x^n).\,$ This Polynomial Congruence Rule. is the congruence analog of the Polynomial Factor Theorem. While you can prove special cases of these results without congruences, they ususally end up being obfuscated unwindings of the simple congruence-based proofs. I strongly recommend mastering the congruence methods, since without them you will soon be lost in more complicated cases. – Bill Dubuque Sep 11 '17 at 14:40

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$

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.

Hint: $8^{x \cdot 2}-5^{x \cdot 2}=(8^x)^2-(5^x)^2=(8^x-5^x)(8^x+5^x)$

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.

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.

• You have got the incorrect $A$ and $B$ when using $A^2 - B^2 = (A-B)(A+B)$. – user99914 Sep 15 '17 at 10:08
• Stupid of me I've got it on my paper but I didn't edit it there. – Anonymous196 Sep 15 '17 at 13:15
• I mean this one: $8^{2^{m+1}} -5^{2^{m+1}} = (8^{m+1} + 5^{m+1})(8^{m+1} -5^{m+1})$. It's incorrect. Note $8^{2^{m+1}} - 5^{2^{m+1}} = (8^{2^m})^2 - (5^{2^m})^2$. – user99914 Sep 15 '17 at 14:27
• Oh, ok. I see now – Anonymous196 Sep 15 '17 at 19:03
• I will change it – Anonymous196 Sep 15 '17 at 19:14

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

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.

• Yeah I've come across telescoping sum and products before but I'd never think of it to use it here in the proof. Interesting way to see that. But what do you need to do to complete this proof? Does one just say because 13 is a product in this telescoping product that is indeed divisible by 13 and then the proof is finished? – Anonymous196 Sep 11 '17 at 15:27
• See this answer for a vivid view of the telescopic cancellation in the above answer. – Bill Dubuque Sep 12 '17 at 15:02
• @AnonymousI Good question. To be rigorous we'd need to prove by induction that $\,13\mid 13\, a_1\cdots a_n,\,$ e.g. by proving that the product of $n$ integers is an integer (possibly a corollary of an earlier (rigorous) recursive definition of products $\,\prod a_i)$. It's instructive to compare to the congruence method: it works simply by squaring $\,8^{\large 2^n}\!\equiv 5^{\large 2^n}$ to get the $n+1$ case, but the above computes their quotient and accumulates it into the total quotient. But computing the quotient is usually (much) wasted effort if only the remainder is needed. – Bill Dubuque Sep 12 '17 at 15:07