<s>[INST] 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?
 [/INST] 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$.
</s>