# elementary congruence statement proof

it is me again :), i am trying to prove this statement of congruence, the statement is as follows:

$a \equiv b \mod m \Longrightarrow a^{k} \equiv b^{k} \mod m$ for all $k \in \mathbb{N}$

i cannot even start the prove, i dont know where to start. can some please help me.

i know the definition of congruence:

$a \equiv b \mod m :\Longleftrightarrow m|a-b$

how can i use it to prove the statement? thanks

-

From your earlier post, you know that if $a\equiv b$ and $c\equiv d \pmod{m}$, then $ac\equiv bd\pmod{m}$.

In particular, with $a$ in place of $c$, and $b$ in place of $d$, you have $a^2\equiv b^2\pmod{m}$. Now you can use an inductive argument to conclude that $a^k\equiv b^k\pmod{m}$ for all $k\in\mathbb{N}$.

-
yeah, my Bad! you are totally right – doniyor Nov 18 '12 at 10:27

you already said it yourself. =D $a \equiv b \mod m$ if and only if $m | a - b$. Now if $a \equiv b \mod m$, then $m | a - b$. Since $a - b | a^k - b^k$, then it follows that $m | a^k - b^k$.

-
wow, great thanks Eric, direkt way of thinking! – doniyor Nov 18 '12 at 10:36

Use the identity

\begin{align*} a^k-b^k&=(a-b)\left(a^{k-1}+a^{k-2}b+a^{k-3}b^2+\ldots+a^2b^{k-3}+ab^{k-2}+b^{k-1}\right)\\ &=(a-b)\sum_{i=0}^{k-1}a^{k-1-i}b^i\;. \end{align*}

The special cases $k=2$ and $k=3$ are probably familiar:

$$a^2-b^2=(a-b)(a+b)$$

and

$$a^3-b^3=(a-b)\left(a^2+ab+b^2\right)\;.$$

-