1. ## Congruences Proof

Prove, by induction: If a and b are congruent mod m, then a^n and b^n are congruent mod m.

2. Recall: $a \equiv b \ (\text{mod } m) \ \Leftrightarrow \ a = b + km$ for some $k \in \mathbb{Z}$

For the inductive step, we assume that it is true for some $k$, i.e $a^k \equiv b^k \ (\text{mod } m)$ and we want to prove that it is also true for $k+1$.

Multiply both sides by $a$ and substitute $a = b + km$ for some integer $k$ (just go by the definition of congruences!)

3. Okay, so I understand that I must show that a^(k+1) and b^(k+1) are congruent mod m.

And I understand that a and b are congruent mod m iff a = b + km, k e Z.

But, Im not sure why I would multiply both sides by a?? And where do I plug in my Inductive Hyp? Is the base case 0?

4. Originally Posted by jzellt
Okay, so I understand that I must show that a^(k+1) and b^(k+1) are congruent mod m.

And I understand that a and b are congruent mod m iff a = b + km, k e Z.

But, Im not sure why I would multiply both sides by a?? And where do I plug in my Inductive Hyp? Is the base case 0?
the base case is n = 1, which is given. we are told $a \equiv b ~(\bmod ~m)$

picking up where o_O left off. we have

$a^k \equiv b^k ~(\bmod ~m)$

$\Rightarrow a^{k + 1} \equiv ab^k ~(\bmod ~m)$ ....by multiplying both sides by $a$

now change the $a$ on the right how o_O said to change it. see what you get

5. So, on the right side we have (b + mk)b^k = b^(k+1) + b^k(mk)

Now what do I do with b^k(mk)??

6. edit: Sorry, I just noticed you are required to use induction. Too bad!
I don't think it is necessary to use induction.

If a and b are congruent modulo n, then a-b is a multiple of n.

For any positive integer n, $a^n- b^n= (a- b)(a^{n-1}+ a^{n-2}b+ a^{n-3}b^2+ \cdot\cdot\cdot+ a^2b^{n-3}+ ab^{n-2}+ b^{n-1}$.

Do you see how that shows that $a^n- b^n$ is a multiple of n?