2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Ohh, thank you. That is exactly what I was looking for. $\endgroup$
    – Meecolm
    Dec 7 '14 at 18:52
  • $\begingroup$ 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. $\endgroup$ Dec 7 '14 at 18:54
0
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Meecolm
    Dec 7 '14 at 18:50
0
$\begingroup$

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)

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – hardmath
    Aug 6 '17 at 18: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.