# Thread: 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 $\displaystyle m = 1$, since that is given.

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

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

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

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

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

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

since $\displaystyle tnb^k \equiv 0 \!\!\!\!\!\pmod{n}$ (since it is a multiple of $\displaystyle 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