Monday, March 21, 2016

modular arithmetic - Show $a^k ≡ b^kpmod m$



I need to show that if $a,b,k$ and $m$ are integers and $k ≥ 1, m ≥ 2$, and $a ≡ b\pmod m$, then: $a^k ≡ b^k \pmod m$.



But I have no idea how to show this, I have never been this confused. So is there anyone who could help? just a little, like I honestly feel overwhelmed (sounds stupid I know, sorry)



*what do i need to do with the m ≥ 2 ???


Answer



I assume you know (all equivalences are $\text{mod } m$)





  1. $a\equiv b \iff a-b\equiv 0$

  2. $c\equiv 0 \implies cd\equiv 0$



Then



$\begin{align}&a\equiv b\\
\iff &a-b\equiv 0\\
\implies &(a-b)(a^{k-1} + a^{k-2}b + \cdots + ab^{k-2}+b^{k-1})\equiv 0\\

\iff &a^k-b^k\equiv 0\\
\end{align}$



The last deduction above is technically hand-waved but can be made formal with a summation or with induction.


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