Tuesday, April 19, 2016

elementary number theory - How to prove $8^{2^n} - 5^{2^n}$ is divisible by $13$ where $ninmathbb{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}$



Can somebody please help me?


Answer



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



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...