Proof : $a\equiv b \pmod n \implies a^i\equiv b^i \pmod n$

Question

The congruence equation $a\equiv b \pmod n \implies \exists k \in \mathbb{Z}, a -b = kn.$
Taking the i-th power of both sides : $(a -b)^i = k^in^i$.

$(a-b)(a-b)^{i-1}=k^in^i$.
$n\mid (a-b), (a-b) \mid (a-b)^i \implies n\mid (a-b)^i \implies \exists m \in \mathbb {Z}, (a-b)^i = mn$.

But, my proof is incomplete, as it does not show still that $a^i - b^i = kn$.

---

All the comments and answer have ignored the fact that how to get the term $a^i - b^i$ in the first place.
It seems that all have taken the approach to simply take the $a^i- b^i=kn$ as a new equality, not derived from the original one. Just it uses the property of $n \mid (a-b)$ of the original one.

Answer 1

It might be easier to use $a = kn + b$ and the Binomial theorem. Then $a^i = (kn+b)^i = \sum_{j=0}^i \binom{i}{j}(kn)^jb^{i-j}$. All of these terms have a factor of $n$ in them except for the $0^{th}$ one, so this equation may be written in the form $a^i = pn + b^i$. Hence the claim.

Answer 2

This is not the easiest answer but hope it will be instructive, as it illustrates some important points:

Lemma: If $a\equiv b\pmod n$ and $c\equiv d\pmod n$, then $ac\equiv bd\pmod n$. (Congruences can be multiplied.)

Proof of the Lemma: $bd-ac=bd-ad+ad-ac=(b-a)d+a(d-c)$. If $n\mid b-a$ and $n\mid d-c$, i.e. $b-a=un, d-c=vn$, then $bd-ac=und+avn=(du+av)n$ and so $n\mid bd-ac$, i.e. $ac\equiv bd\pmod n$.

Proof of the claim: by induction on $i$:

• $i=0$: $a^0=1\equiv 1=b^0\pmod n$ - trivially
• $i\to i+1$: If $a\equiv b\pmod n$ and $a^i\equiv b^i\pmod n$ (inductive hypothesis), then by using Lemma, and multiplying those congruences, we get the congruence $a^{i+1}\equiv b^{i+1}\pmod n$.

Answer 3

$$a\equiv b \pmod n \implies n|(b-a)$$

$$n|(b-a),\text { and } (b-a)|(b^i-a^i) \implies n| (b^i-a^i) $$

$$ n| (b^i-a^i) \implies a^i\equiv b^i \pmod n$$

Answer 4

I think it is easiest first to prove

Prop: If $a \equiv b \mod n$ and $c \equiv d \mod n$ then $ac \equiv bd \mod n$.

Proof: $n|(a-b)$ so $a-b = kn$ so $a = b + kn$ for some integer $k$. And $n|c-d$ so $c-d = jk$ so $c = d + jn$ for some integer $j$. So $ac =(b+kn)(d+jn) = bd + kdn + bjn + kjn^2 = bd + n[dk + bj + kjn]$ so $ac - bd = n[dk + bj + kjn]$ so $n|ac-bd$ so $ac\equiv bd \mod n$.

Then by induction, If $a_i \equiv b_i \mod n$ for several $a_i$ and $b_i$ then $a_1*a_2*..... * a_n\equiv b_1*b_2*....*b_n \mod n$.

SO if $a\equiv b \mod n$ then $a*a \equiv b*b \mod n$ and $(a*a)*a \equiv (b*b)*b \mod n$, etcc. so $a^i \equiv b^i \mod n$.

==== or =====

$a\equiv b \mod n$ means $(b-a) = n*k$ for some integer $k$.

$b^i - a^i = (b-a)(b^{i-1}+ b^{i-2}a + ..... + ba^{i-2} + a^{i-1})$

So $b^i - a^i = (n*k)(b^{i-1}+ b^{i-2}a + ..... + ba^{i-2} + a^{i-1})$

$= n*[k(b^{i-1}+ b^{i-2}a + ..... + ba^{i-2} + a^{i-1})]$.

Now, clearly you must agree than $[k(b^{i-1}+ b^{i-2}a + ..... + ba^{i-2} + a^{i-1})]$ is an integer!

SO $n|(b^i - a^i)$.

So $a^i \equiv b^i \mod n$.

Answer 5

$a≡ b\mod n ⇒ a= k.n +b; k∈ N $

⇒ $a^i=(kn+b)^i= k_1.n+b^i; k_1∈ N ⇒ a^i ≡ b^i \mod n$