Prove that $(a-b) \mid (a^n-b^n)$ [duplicate]

Question

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!

Answer 1

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!

Answer 2

Observe:

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

Answer 3

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

Answer 4

É ó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}.$

Answer 5

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

Answer 6

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.