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
24  
$(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

5 Answers 5

up vote 24 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 at 0:37
    
Or rather the fourth step. I'm on my phone so it loads strangely sometimes. –  TylerHG Jun 5 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

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.