35
$\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?

  • 34
    $(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\cdots+b^{n-1})=a^n-b^n$.2012-08-30
  • 0
    Because when you take b = a you get zero.2015-05-14
  • 0
    @z_z: Related http://math.stackexchange.com/questions/695266/factoring-xn-yn-over-the-integers2016-08-26
  • 0
    See also: [Prove that $(a-b) \mid (a^n-b^n)$](https://math.stackexchange.com/q/430645).2017-09-15

8 Answers 8

32

They are all special cases of the Factor Theorem: $\rm\: x-y\:$ divides $\rm\:f(x)-f(y),\:$ for $\rm\:f\:$ a polynomial with integer coefficients, i.e. $\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$

21

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

20

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
    I think your proof is clever. However, I think the fact that $(x-b)$ divides $f(x)$ is not entirely trivial.2012-08-30
  • 0
    This is a well known result from algebra which says: If $f(x)\in F[x]$, where $F$ is a field, then $\alpha\in F$ is a root of $f(x)$ if and only if $(x-\alpha)|f(x)$2012-08-30
  • 0
    Of course it is. But that does not mean its proof is easier. Also, the fact you are really using is that division by monic polynomials holds in any ring, not just a field. If $x^n - b^n = (x-b)g(x)$, you really want the coefficients of $g(x)$ to be in $\mathbb{Z}$ as otherwise $g(a)$ is not guaranteed to be an integer.2012-08-30
  • 0
    Sorry, I am just being nitpicky. I think your solution is very nice.2012-08-30
12

Since you originally observed your patter 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
    Are you absorbing $b$ into $k$ on the third line of the proof? @Rankeya2014-06-05
  • 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
    There's a good proof along these lines, but you didn't give it; it appears like you just pulled the second line out of the blue (the one with the red font). How do you get from the first line to the second line?2015-05-14
  • 0
    Well, I just substituted $r=b/a$ in the first equation. $a^n$ cancels from both sides, and the resulting equation is the one on the second line. Does that make it clearer?2015-05-15
  • 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