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: $\displaystyle a \equiv b \ (\text{mod } m) \ \Leftrightarrow \ a = b + km$ for some $\displaystyle k \in \mathbb{Z}$

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

Multiply both sides by $\displaystyle a$ and substitute $\displaystyle a = b + km$ for some integer $\displaystyle 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 $\displaystyle a \equiv b ~(\bmod ~m)$

picking up where o_O left off. we have

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

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

now change the $\displaystyle 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, $\displaystyle 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 $\displaystyle a^n- b^n$ is a multiple of n?