If $a > b+1$ then there is $M > 1$ so that $a^n - b^n$ is divisible by $M$ for all positive integers $n$. Prove by induction that $M = a - b$.

The problem:

It turns out that if $a$ and $b$ are positive integers with $a > b + 1$, then there is a positive integer $M > 1$ such that a $a^n − b^n$ is divisible by $M$ for all positive integers $n$. Determine $M$ in terms of $a$ and $b$ and prove that it is a divisor of $a^n − b^n$ for all positive integers $n$.

I am fairly certain $M=a-b$, however, I am having trouble proving it $\forall \ n \in \Bbb N$. Here is my thought process:

Base case: Let $a,b \in \Bbb Z$, $n=1$, then $a^n-b^n = a - b = M$ as desired.

Inductive hypothesis: Assume true for $k$ such that $1 \le k \le n$.

$a^k - b^k = M(m)$, where $m \in \Bbb Z$.

Inductive step:

$a^{k+1} + b^{k+1} = aa^k - bb^k = (a-b) + (a-1)a^k-(b-1)b^k = M + (a-1)a^k-(b-1)b^k$

That is as far as I got, I tried a lot of things but I can't seem to factor out $(a-b)$ from $(a-1)a^k-(b-1)b^k$.

Thank you in advance for any help.

Hint: One way to do the induction step is to note that $$a^{k+1}-b^{k+1}=a^{k+1}-ba^k +ba^k-b^{k+1}=a^k(a-b)+b(a^k-b^k).$$

It follows quickly from the induction hypothesis that $a-b$ divides the right-hand side, and hence the left-hand side.

• Ohh, thank you. That is exactly what I was looking for. Dec 7 '14 at 18:52
• You are welcome. Yes, you came close but somehow ended up trying to do a hybrid induction, with $a$ varying. In the proof, $a$ and $b$ are fixed. Dec 7 '14 at 18:54

I think induction is probably not useful for this problem. You already started with $a^n-b^n=M \cdot m=(a-b)m$. Maybe you could try to directly determine $m$ in terms of $a,b,n$. (Hint: Polynomial Division)

• I think that would be useful but as a note the problem is one of a set in which I am supposed to use induction strictly. Dec 7 '14 at 18:50

Determine M in terms of a and b and prove that it is a divisor of a^n - b^n for all positive integer n. click on the link to see the solution...(https://i.stack.imgur.com/Io3Mo.jpg)

• A better way to include mathematical expressions in your posts is with MathJax and $\LaTeX$. See this brief introduction and its links to more detailed information. Aug 6 '17 at 18:47