Why is $a^n - b^n$ divisible by $a-b$?

Question

I did some mathematical induction problems on divisibility

• $9^n$ $-$ $2^n$ is divisible by 7.
• $4^n$ $-$ $1$ is divisible by 3.
• $9^n$ $-$ $4^n$ is divisible by 5.

Can these be generalized as $a^n$ $-$ $b^n$$ = (a-b)N$, where N is an integer? But why is $a^n$ $-$ $b^n$$ = (a-b)N$ ?

I also see that $6^n$ $- 5n + 4$ is divisible by $5$ which is $6-5+4$ and $7^n$$+3n + 8$ is divisible by $9$ which is $7+3+8=18=9\cdot2$.

Are they just a coincidence or is there a theory behind?

Is it about modular arithmetic?

Answer 1

They are all special cases of the Polynomial Factor Theorem: $\rm\: x-y\:$ divides $\rm\:f(x)-f(y),\:$ here for $\rm\,f\,$ a polynomial with integer coefficients, so $\rm\:f(x)-f(y) = (x-y)\:g(x,y)\:$ for a polynomial $\rm\:g\:$ with integer coefficients. The prior equation (so the divisibility) remains true when we evaluate the indeterminates $\rm\:x,y\:$ at integer values. This yields your examples by choosing $\rm\:f(z) = z^n.$

Said simpler: $\rm\: mod\,\ x\!-\!y\!:\ \ x\equiv y\,\Rightarrow f(x)\equiv f(y)\ $ by the Polynomial Congruence Rule.

for example: $\ \rm\ mod\,\ 9\!-\!4\!:\ \ 9\equiv 4\:\Rightarrow\ 9^n\equiv\, 4^n\ $ (alternatively by the Congruence Power Rule).

Note that the all linked proofs proceed by induction on $\rm\,n\,$ (= polynomial degree).

Answer 2

It can be generalized as:

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

If you are interested in a modular arithmetic point of view, since $a \equiv b \pmod{a-b},$ $a^n \equiv b^n \pmod{a-b}.$

Your last two examples are true because what you are essentially doing is plugging in $n=1.$

Answer 3

It’s a standard identity:

$$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\ldots+a^2b^{n-3}+ab^{n-2}+b^{n-1})\;.$$

It’s most neatly verified using summation notation, but you can also see what’s going on when you write everything out in extended form, as I did above. First,

$$\begin{align*} a(a^{n-1}&+a^{n-2}b+a^{n-3}b^2+\ldots+a^2b^{n-3}+ab^{n-2}+b^{n-1})\\ &=a^n+a^{n-1}b+a^{n-2}b^2+\ldots+a^3b^{n-3}+a^2b^{n-2}+ab^{n-1}\;.\tag{1} \end{align*}$$

Next,

$$\begin{align*} b(a^{n-1}&+a^{n-2}b+a^{n-3}b^2+\ldots+a^2b^{n-3}+ab^{n-2}+b^{n-1})\\ &=a^{n-1}b+a^{n-2}b^2+a^{n-3}b^3+\ldots+a^2b^{n-2}+ab^{n-1}+b^n\;.\tag{2} \end{align*}$$

Now subtract $(2)$ from $(1)$:

$$\begin{align*} a^n&+\color{red}{a^{n-1}b+a^{n-2}b^2+\ldots+a^3b^{n-3}+a^2b^{n-2}+ab^{n-1}}\\ &\color{red}{-a^{n-1}b-a^{n-2}b^2-\ldots-a^3b^{n-3}-a^2b^{n-2}-ab^{n-1}}-b^n\;; \end{align*}$$

the red terms cancel out leaving $a^n-b^n$.

Answer 4

Since you originally observed your pattern while doing proofs by induction, here is a proof by induction on $n$ that $a-b$ divides $a^n - b^n$ for all $n \in \mathbb{N}$:

The statement is clearly true for $n = 1$. Assume the statement is true for $n = m$ for $m \geq 1$. Thus, $a^m - b^m = (a-b)k$, for some $k \in \mathbb{Z}$. Then for $n = m + 1$, \begin{equation} a^{m+1} - b^{m+1} = a^{m+1} - b^mb = a^{m+1} + [(a-b)k - a^m]b = a^{m+1} - a^mb + (a-b)k = a^m(a - b) + (a-b)k = (a-b)(a^m + k). \end{equation} And voila, $a-b| a^{m+1} + b^{m+1}$, so you are done by induction.

Answer 5

Consider the polynomial $f(x)=x^n-b^n.$ Then $f(b)=b^n-b^n=0.$ So $b$ is a root of $f$ and this implies $(x-b)$ divides $f(x)$. Put $x=a$, then $a-b$ divides $f(a)=a^n-b^n.$