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

$\endgroup$
33
$\begingroup$

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$

$\endgroup$
23
$\begingroup$

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

$\endgroup$
20
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ Are you absorbing $b$ into $k$ on the third line of the proof? @Rankeya $\endgroup$ – ClassicStyle Jun 5 '14 at 0:37
  • $\begingroup$ Or rather the fourth step. I'm on my phone so it loads strangely sometimes. $\endgroup$ – ClassicStyle Jun 5 '14 at 0:52
10
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Dustan Levenstein May 14 '15 at 14:59
  • $\begingroup$ 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? $\endgroup$ – udax May 15 '15 at 16:24
  • $\begingroup$ 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$. $\endgroup$ – Dustan Levenstein May 15 '15 at 16:30
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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!! $\endgroup$ – Freelancer Nov 15 '15 at 2:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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