# Proof of $a \equiv b \mod n$ implies $a^k \equiv b^k \mod n$

Prove that for $n$ in the set of natural numbers, with $n \geq 2$: For all $a, b \in \mathbb{N}$, $a \equiv b \mod n$ implies that $a^2 \equiv b^2 \mod n$.

also what about this Prove by induction that for $n$ in the set of natural numbers, $n \geq 2$ For all $a,b \in \mathbb{N}$, $a \equiv b \mod n$ implies that $a^k \equiv b^k \mod n$.

Note that you have that $$a^k - b^k = (a-b)(a^{k-1} + a^{k-2}b + \ldots + ab^{k-2} + b^{k-1}).$$

Now if $a \equiv b \mod n$, then we have that $a = b + kn$ for some $k \in \mathbb{Z}$ and hence we have that $a - b = kn$. Therefore we have that $$n \mid (a-b)$$ and this implies that $$n \mid (a-b)(a^{k-1} + a^{k-2}b + \ldots + ab^{k-2} + b^{k-1}) = a^k - b^k.$$ Therefore, we have that $rn = a^k -b^k$ for some $r \in \mathbb{Z}$ and hence $$a^k \equiv b^k \mod n.$$

• I have corrected the exponents of my first expression (since I made an error over there). This should make my proof correct. However, I have no idea on why you had to prove this using induction. Was this the problem statement or was this your first idea on how to solve this? (just curious) Commented Mar 9, 2017 at 14:53

$a\equiv b\pmod{n}\iff n\mid a-b$

$\implies n\mid (a-b)(a+b)=a^2-b^2\iff a^2\equiv b^2\pmod{n}$

• this is a special case k = 2.
– john
Commented Sep 14, 2020 at 4:47

I hope that you are not required to use induction to prove this, since it's a very special case of a standard theorem at the start of studying modular arithmetic:

If $$a \equiv a' \pmod{n}$$ and $$b \equiv b' \pmod{n}$$ then $$a+b \equiv a'+b' \pmod{n}$$ and $$ab \equiv a'b' \pmod{n} .$$

$a\equiv_n b\implies a-b\equiv_n 0$. What does this say about $n$ being a factor of $a-b$?

If we factor $a^2-b^2$, is there anything we can use from what I just previously mentioned to show the congruence?

Okay, so first let's make a preposition for a^k ≡ b^k, and let's call it P(k). Once we have that, we can move on to our base case. Our base case would be P(0), or when a^0 ≡ b^0 (mod m). That would equal 1 ≡ 1 (mod m). That is true, since, based off of definition, m | (1 - 1), and that equals m | 0, which is true, since m * 0 = 0, so our base case is true. Now it is time for the inductive step. For whenever k ≥ 0, we would have to assume that P(k) in order to prove that P(k + 1) is true. So then assume that a^k ≡ b^k (mod m) is true. When we combine these assumptions and the fact that if a ≡ b (mod m) and c ≡ d (mod m) are true, then a + c ≡ b + d (mod m) would also be true, we would get a^(k + 1) ≡ b^(k + 1) (mod m), so this would therefore be proven by using proof by induction.