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

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.$

Answer 4

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 5

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 6

Just to offer a different perspective, here's a combinatorial argument: Let $\mathcal{A}$ be the set of words of length $n$ on some alphabet $A$ of size $a$, and $\mathcal{B}$ be the set of words of length $n$ on an alphabet $B\subsetneq A$ of size $b\lt a$. Then $|\mathcal{A}|=a^n$, $|\mathcal{B}|=b^n$, and since $\mathcal{B}\subset\mathcal{A}$, if we set $S=\mathcal{A}-\mathcal{B}$ then $|S|=a^n-b^n$.

But now consider some $s\in S$; any such word will have a 'first position' where it has a letter in $A-B$, and we can partition $S$ into $|A|-|B|=a-b$ subsets based on the value of this first letter not in $B$. There's an obvious isomorphism between these sets (just replace that first letter by any other letter not in $B$), and so they're all of the same size; since there are $a-b$ of them total and they equipartition a set of size $a^n-b^n$, then it must be the case that $(a-b)\mid (a^n-b^n)$.

Answer 7

Another proof:

Denote $r=b/a$. We know that the sum of a geometric progression of the type $1+r+r^2+\ldots+r^{n-1}$ is equal to $\frac{1-r^n}{1-r}$. Thus, we have \begin{align} 1-r^n&=(1-r)(1+r+r^2+\ldots+r^{n-1}),\quad\text{substituting $r=b/a$ gives:}\\ a^n-b^n &= (a-b)\color{red}{(a^{n-1}+a^{n-2}b+\ldots+b^{n-1})}\\ a^n-b^n &= (a-b)N \end{align} The last step follows since $a,b$ are integers and a polynomial expression of the type in $\color{red}{red}$ font is also an integer.

Answer 8

Let $d=a-b$. By the binomial theorem, $a^n = (d+b)^n = dt+b^n$. So $a^n-b^n=dt=(a-b)t$.