Take the 2-minute tour ×
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|improve this question
25  
$(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. –  Luis Gomez Sanchez May 14 at 15:04

7 Answers 7

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|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|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|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|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:

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

share|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|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 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|improve this answer

Your Answer

 
discard

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.