If $a-b$ is a multiple of $c$, then $a^n - b^n$ is a multiple of $c$

Question

So I'm stuck doing this problem. Since we have to use induction, I have gotten as far as the base step and then realized that I'm going about this wrong. Here's the problem:

If $a, b, c \in \mathbb{N}$ such that $a-b$ is a multiple of $c$, prove that $a^n - b^n$ is a multiple of $c$ for all $n \in \mathbb{N}$

Please help.

Answer 1

Hint: $$a^{n+1}-b^{n+1}=a(a^n-b^n)+b^n(a-b)\ .$$

Answer 2

We use induction on $n$, with a base case of $n=1$.

---

Base Case

We are given that $a-b$ is a multiple of $c$. Equivalently, there exists a $k_1 \in \mathbb{N}$ such that $$k_1c = a-b = a^1-b^1$$

Inductive Step

Suppose that $a^n-b^n$ is a multiple of $c$. Then there exists a $k_2 \in \mathbb{N}$ such that $a^n-b^n = k_2c$.

As David pointed out, $$a(a^n-b^n)+b^n(a-b)=a^{n+1}-b^{n+1}$$

Substitution gives $$a(k_2c)+ b^n(k_1c)=a^{n+1}-b^{n+1}$$

By associativity of multiplication,

$$(ak_2)c+(b^nk_1)c=a^{n+1}-b^{n+1}$$

By the distributive property,

$$(ak_2+b^nk_1)c=a^{n+1}-b^{n+1}$$

Since $\mathbb{N}$ is closed under addition and multiplication, $(ak_2+b^nk_1) \in \mathbb{N}$, so $a^{n+1}-b^{n+1}$ is a multiple of $c$.

---

This proves that for all $n \in \mathbb{N}$, $$c\mid (a^n-b^n)$$

Answer 3

Hint: $$a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + \cdots+ ab^{n-2} + b^{n-1}$$