# Math Help - inductive proof on a (mod n) type problem

1. ## inductive proof on a (mod n) type problem

Hi,

Prove by induction that if n is a N and a,b is a Z and a congruent b(mod n), then a^m congruent b^m (mod n).

then a = nk - b and use this fact in a^m -b^m = nk by rewriting it as aa^(m-1) - bb^(m-1) = 2k by subbing a into it. This did not work after multiple attempts. I am quite frustrated.

2. Originally Posted by pberardi
Hi,

Prove by induction that if n is a N and a,b is a Z and a congruent b(mod n), then a^m congruent b^m (mod n).

then a = nk - b and use this fact in a^m -b^m = nk by rewriting it as aa^(m-1) - bb^(m-1) = 2k by subbing a into it. This did not work after multiple attempts. I am quite frustrated.
It said use induction, so here goes.

Base case: Clearly the claim is true for $m = 1$, since that is given.

Induction hypothesis: Assume the claim is true for some $k$, that is $a^k \equiv b^k \!\!\!\!\!\pmod{n}$. We show that the claim is true for $k + 1$, that is, $a^{k + 1} \equiv b^{k + 1} \!\!\!\!\! \pmod{n}$.

Since $a \equiv b \!\!\!\!\!\pmod{n}$, we have that $a = b + tn$, for some integer $t$

Now $a^k \equiv b^k \!\!\!\!\!\pmod{n}$

$\Rightarrow a \cdot a^k \equiv a \cdot b^k \!\!\!\!\!\pmod{n}$

$\Rightarrow a^{k + 1} \equiv (b + tn)b^k \!\!\!\!\!\pmod{n}$

$\Rightarrow a^{k + 1} \equiv b^{k + 1} + tnb^k \!\!\!\!\!\pmod{n}$

since $tnb^k \equiv 0 \!\!\!\!\!\pmod{n}$ (since it is a multiple of $n$) we have the desired result.

3. what i dont understand is the first arrow line of your proof. Did you just multiply both sides by a?

4. Originally Posted by pberardi
what i dont understand is the first arrow line of your proof. Did you just multiply both sides by a?
yes