Proof that congruence is compatible with powers

Proof

We argue by induction on $k$.

1. Let $n$ be a positive integer, and let $a$ and $b$ be integers with $a \equiv b \pmod n$.
2. Base case $k = 0$: we have $a^0 = 1 = b^0$. Since $n$ divides $1 - 1 = 0$, we get $a^0 \equiv b^0 \pmod n$ by the definition of congruence.
3. Induction step: let $k \ge 0$ and assume $a^k \equiv b^k \pmod n$.
4. By step 3, by step 1 and by compatibility with multiplication, $a^k \cdot a \equiv b^k \cdot b \pmod n$.
5. That is, $a^{k+1} \equiv b^{k+1} \pmod n$.
6. By steps 2 to 5 and induction, $a^k \equiv b^k \pmod n$ for each natural number $k$.