40
$\begingroup$

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?

  • 0
    See also: [Prove that $(a-b) \mid (a^n-b^n)$](https://math.stackexchange.com/q/430645).2017-09-15

8 Answers 8

36

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 divisibility relation remains true when one evaluates the indeterminates $\rm\:x,y\:$ at integer values (this yields your examples if we let $\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$

24

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

21

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

  • 0
    Sorry, I am just being nitpicky. I think your solution is very nice.2012-08-30
12

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.

  • 0
    Or rather the fourth step. I'm on my phone so it loads strangely sometimes.2014-06-05
10

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

4

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

2

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.

  • 0
    I'm saying you should make that step more explicit. Literally, include the line $1-(b/a)^n = (1-(b/a))(1+(b/a)+\ldots+(b/a)^{n-1})$, and then multiply by $a^n$.2015-05-15
1

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

  • 0
    Well...that's a good way to look at it..and even though it satisfied the need of the question...but unfortunately it doesn't talk much about the term( $t$)...which would have been really good!!2015-11-15