9
$\begingroup$

I'm trying to prove by induction that for all $a,b \in \mathbb{Z}$ and $n \in \mathbb{N}$, that $(a-b) \mid (a^n-b^n)$. The base case was trivial, so I started by assuming that $(a-b) \mid (a^n-b^n)$. But I found that: \begin{align*} (a-b)(a^{n-1}+a^{n-2}b + a^{n-3}b^2+...+b^{n-1}) &= a^n-b^n. \end{align*}

Doesn't this imply that $(a-b) \mid (a^n-b^n)$ as $a^{n-1}+a^{n-2}b+\dots+b^{n-1}$ is clearly an integer? This obviously isn't a proof by induction, but is there anything wrong with taking this approach to prove this result, other than the fact that it isn't what is being asked?

Aside, I'm having trouble getting started with the proof by induction. I've tried making the above equivalence useful during the induction step, but it doesn't seem to be helpful, so any hints would be greatly appreciated!

$\endgroup$
  • 4
    $\begingroup$ You have found an identity that proves the divisibility. But how do you prove the identity? It depends on $n$. You can use induction! Hint: $a^n-b^n=a(a^{n-1}-b^{n-1})+(a-b)b^{n-1}$. $\endgroup$ – Aaron Jun 27 '13 at 8:57
  • 1
    $\begingroup$ The downside of this option is that the proposed cofactor is written with "$\ldots$", which is not rigorous. If you write that with a proper summation using $\Sigma$, one ends up with a nice proof (though induction is still hidden in it). $\endgroup$ – Hagen von Eitzen Jun 27 '13 at 9:50
  • $\begingroup$ @HagenvonEitzen I see, that was pretty much what I was wondering about. I thought I had read somewhere that using "$\dots$" was not rigorous. Thanks! $\endgroup$ – stochasm Jun 27 '13 at 17:00
  • $\begingroup$ See also: Why $a^n - b^n$ is divisible by $a-b$? $\endgroup$ – Martin Sleziak Sep 15 '17 at 14:21
14
$\begingroup$

The induction step can be handled by observing that $a^{(k+1)} - b^{(k+1)} = aa^k - ab^k + ab^k - bb^k = a(a^k - b^k) + (a - b)b^k$. Then by the inductive hypothesis, $a - b$ divides each summand.

Would say more but I must crash. Perhaps I can add the details of the full inductive proof manana. But it should be easy from here . . .

G'night, fellow math-heads!

| cite | improve this answer | |
$\endgroup$
11
$\begingroup$

Observe:

$a - b \equiv 0 \pmod {a-b} \implies a\equiv b \pmod{a-b} \implies a^n \equiv b^n \pmod{a-b} $

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Yes your proof is obviously correct. To use induction, suppose your statement is true for $n$. Then you want to show that $(a-b)\mid (a^{n+1}-b^{n+1})$. By induction hypothesis, there is an integer $k$ s.t. $a^n-b^n=k(a-b)$. Now try to substitute the value for $a^n$ that you obtain this way inside the expression $a^{n+1}-b^{n+1}$ and see what happens...

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

É óbvio que a afirmação é verdade para $n = 0$, pois $a−b$ divide $(a^0)−(b^0) = 0$. Suponhamos, agora, que $a − b\mid a^n − b^n$. Escrevamos $$a^{n+1} − b^{n+1} = a\times a^n − b\times a^n + b\times a^n − b\times b^n = (a − b)a^n + b(a^n − b^n).$$ Como $a−b\mid a−b$ e, por hipótese, $a−b\mid a^n−b^n$, decorre da igualdade acima e pela proposição: Se $a, b, c \in\mathbb{N}$, com a $a\neq 0$, e $x, y \in\mathbb{N}$ são tais que $a\mid b$ e $a\mid c$, então $a\mid (xb + yc)$; e se $xb \geq yc$, então $a\mid (xb − yc).$ Logo, $a−b\mid a^{n+1} −b^{n+1}$, estabelecendo o resultado para todo $n\in\mathbb{N}$.


It is obvious that the affirmation is true for $n=0$, because $a-b$ divides $(a^0)−(b^0) = 0.$ Suppose now that $a − b\mid a^n − b^n.$ Write $$a^{n+1} − b^{n+1} = a\times a^n − b\times a^n + b\times a^n − b\times b^n = (a − b)a^n + b(a^n − b^n).$$ It is clear that $a−b\mid a−b$ and, by our hypothesis, $a−b\mid a^n−b^n$ follows from the previous identity and by this proposition: for every $a, b, c, x, y \in \mathbb{N}$, $a\neq 0$, $$a\mid b \land a\mid c \implies a\mid (xb + yc)$$ and if $xb ≥ yc$, then $a\mid (xb − yc).$ Then $a−b\mid a^{n+1} −b^{n+1}$, establishing the result $\forall n\in \mathbb{N}.$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I translated this answer from Portuguese to English, trying to keep the reasoning unchanged. See how to use LaTeX here $\endgroup$ – Ian Mateus Jun 27 '13 at 20:38
  • $\begingroup$ You can make $a^n+1$ look like $a^{n+1}$ by enclosing the $n + 1$ in braces. See any Latex reference for more. $\endgroup$ – Robert Lewis Jun 28 '13 at 2:37
2
$\begingroup$

The polynomial $(a^n-b^n)$ over values of $n$ can actually be treated as a base. That is, there are characteristic divisors for each integer $m$, which divides this equation when $m=m$.

The equation $a^n-b^n$ has a distinct algebraic divisor for each $m \ n$, this algebraic divisor appears every time $m$ divides $n$.

Although you can use algebra to sort this, it is usually faster to use a sample base, like 10. This means that the values can be found by a calculator. In the following table, one calculates the unique factor in 9, 99, 999, etc, dividing by the unique factors for all of the proper divisors (eg $999999 /( 9 * 11 * 111) = 91$. The next step is to add a string of '$5$'s. This has the effect of creating 'negative digits', eg $4 \text{ ~} -1$.

Now you can read the polynomial off by subtracting 5 from each place in turn, and treating the place as $a^x b^{n-x}$, where the value had been $10^x$. You then get the desired polynomial. I used this system to generate all of these kind of numbers as far as 162 places programically.

       1        9       555564              1,-1
       2       11       555566              1, 1
       3      111       555666           1, 1, 1
       4      101       555656           1, 0, 1
       6       91       555646           1, -1, 1
       5    11111       566666          1,1,1,1,1
       8    10001       565556          1,0,0,0,1
      10     9091       565456          1,-1,1,-1,1
      12     9901       565456          1,0,-1,0,1

The kind of system where $a$ and $b$ are integers, are fractional bases. You can find, for example, that $37 \mid 1,1,1$ for $a=15, b=2$, and some of the 37ths actually have 3-place periods in that base.

The same rules that governs ordinary bases (eg $p \mid b^{p-1}-1)$ also happens for fractional bases, since one can write $B = a/b$ and multiply through by a power of $b$ throughout.

Another way to prove things is to write $a^{mn}-b^{mn}$ as $(a^m)^n - (b^m)^n$, and then put $A$, $B$ for the expressions in brackets: $A^n-B^n$. This is similar to considering base $1000$ as a power of $10$. So, eg in base $1000$, we have $999 \mid 1000^n-1$, and thus $111 \mid 10^{3n}-1$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Doesn't this imply that (a−b)∣(an−bn)(a−b)∣(an−bn) as an−1+an−2b+⋯+bn−1an−1+an−2b+⋯+bn−1 is clearly an integer? This obviously isn't a proof by induction, but is there anything wrong with taking this approach to prove this result, other than the fact that it isn't what is being asked?

Well, the only way to make that proof complete is to handle that "$\ldots$" you wrote by using induction. So you're right, but you still need induction.

| cite | improve this answer | |
$\endgroup$

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.