$\begingroup$

I wish to prove that for integers $a,b$ it is always true that $a-b$ divides $a^n-b^n$. I want to do this via induction. For our base case $n=1$ it holds that $a-b|a-b$. Our hypthesis would be that for some $k$ we know $a-b|a^k-b^k$ or equivalently for some integer l:$$a^k-b^k =l (a-b) $$ How would I use this to prove that:$$a^{k+1}-b^{k+1} =l' (a-b) $$

I was thinking I could use some clever factoring or something like the binomial theorem, but not quite sure. Could someone provide a tiny hint?

$\endgroup$ 2

4 Answers

$\begingroup$

You can use $$a^{k+1}-b^{k+1}=a(a^{k}-b^{k})+b^{k}(a-b).$$

$\endgroup$ 2 $\begingroup$

Add and subtract $ab^n$ from $a^{n+1} - b^{n+1}$.

Note that, $aa^{n} - ab^n + ab^n - bb^{n}$ = $a(a^n - b^n) + (a-b)b^n$. Now you can easily see that this term is divisible by $(a-b)$.

$\endgroup$ $\begingroup$

Hint:

Try to use Euclid's division algorithm to divide the polynomial $$X^k-1$$ by $X-1$. Do you see a pattern for different $k$'s?

If so, use the induction to prove your hypothesis. You get something of the form $$X^k-1 = (X-1)Q(X)$$ for some polynomial $Q(X)$. Let now $X = \frac{a}{b}, b\neq 0$.

$\endgroup$ $\begingroup$

Strong induction may be more natural here.

The base case is $n=1,2$. This is true since $a-b|a-b$ and $a-b|a^2-b^2=(a-b)(a+b)$.

Assume that it's true for $n=1,2,..k$. Then,$$a^{k+1}-b^{k+1}=(a+b)(a^k-b^k)-ab(a^{k-1}-b^{k-1})$$

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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