# Show $a^k ≡ b^k\pmod 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 ???

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.

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

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