Why is $a^n - b^n$ divisible by $a-b$? 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?
 A: 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)$.
A: 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).
A: 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.
A: 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.$
A: 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.$
A: 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$.
A: 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$.
A: 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.
