1
$\begingroup$

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

3 Answers 3

2

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

  • 0
    yeah, my Bad! you are totally right2012-11-18
4

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

  • 0
    wow, great thanks Eric, direkt way of thinking!2012-11-18
2

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)\;.$

  • 0
    Thanks Brian, i was not thinking about this..2012-11-18