0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Hint: For $k≥1$,

$a^k-b^k$ is divisible by $a-b$.

That is, $a≡b \pmod m$ implies $m$ divides $a-b$.

And also $a-b$ divides $a^k-b^k$, thus by transitivity, $m$ divides $a^k-b^k$.

(i.e) $a^k ≡ b^k\pmod m$.

Note: $(a-b)(a^{k-1} + a^{k-2}b + \cdots + ab^{k-2}+b^{k-1})=a^k-b^k$

$\endgroup$
0
$\begingroup$

$a \equiv b \pmod m$ means $a = b+vm$ for some integer $v$.

So $a^k = (b + vm)^k = \sum_{j=0}^k {k\choose j}(vm)^jb^{k-j}$ by the binomial theorem.

The trick is that for each $j \ge 1$ that ${k\choose j}(vm)^jb^j$ is a multiple of $m$.

So $(b + v*m)^k = b^k + \sum_{j=1}^k {k\choose j}(vm)^jb^{k-j}\equiv b^k \pmod m$

So $a^k = (b + v*m)^k \equiv b^k \pmod m$

(If you really care $a^k = b^k + m*K$ where $K = \sum_{j=1}^k {k\choose j}v^jm^{j-1}b^{k-j}$. )

.....

Actually I find it easier to just do the product rule.

If $a \equiv c\pmod m$ and $b \equiv d\pmod m$ then $ab \equiv cd \pmod m$. Because there are integers $k,j$ so that $a = c + km$ and $b = d + jm$.

So $ab = cd + cjm + dkm + jkm^2 = cd + m(cj + dk + jkm)$.

So $ab \equiv cd \pmod m$.

So by induction we know that if $a \equiv b \pmod m$ then $a^2 = a\cdot a \equiv b\cdot b\pmod m = b^2$ and via induction $a^k = a^{k-1}\cdot a \equiv b^{k-1}\cdot b \pmod k= b^k$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.