So the question is as above is shown:
How to prove 82n−52n is divisible by 13?
n=1:82−52=39 is a multiple of 13.
I.H.: Suppose 82n−52n is divisible by 13 is true ∀n∈N∖{0}.
I got stuck on this n=m+1 case.
82m+1−52m+1=82m⋅2−52m⋅2
Can somebody please help me?
Answer
mod 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