Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|cite|improve this question
$(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\cdots+b^{n-1})=a^n-b^n$. – Gerry Myerson Aug 30 '12 at 3:09
Because when you take b = a you get zero. – Ataulfo May 14 at 15:04

9 Answers 9

up vote 25 down vote accepted

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

for example: $\rm\ mod\ 9\!-\!4\!:\ \ 9\equiv 4\:\Rightarrow\: 9^n\equiv 4^n$

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer
I think your proof is clever. However, I think the fact that $(x-b)$ divides $f(x)$ is not entirely trivial. – Rankeya Aug 30 '12 at 6:13
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)$ – pritam Aug 30 '12 at 6:18
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. – Rankeya Aug 30 '12 at 6:36
Sorry, I am just being nitpicky. I think your solution is very nice. – Rankeya Aug 30 '12 at 6:43

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.

share|cite|improve this answer
Are you absorbing $b$ into $k$ on the third line of the proof? @Rankeya – TylerHG Jun 5 '14 at 0:37
Or rather the fourth step. I'm on my phone so it loads strangely sometimes. – TylerHG Jun 5 '14 at 0:52

It’s a standard identity:


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*}$$


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

share|cite|improve this answer

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.

share|cite|improve this answer
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? – Dustan Levenstein May 14 at 14:59
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? – udax May 15 at 16:24
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$. – Dustan Levenstein May 15 at 16:30

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

share|cite|improve this answer

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

share|cite|improve this answer
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!! – Freelancer Nov 15 at 2:47

Just because when $a=b$, you have $a-b=0$ and $a^n-b^n=0$, so that $a^n-b^n$ can be factored as $(a-b)(\cdots)$.

share|cite|improve this answer
Please explain the downvote. – Yves Daoust Nov 16 at 10:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.