I'm working on a problem that's given me the run around for about a weekend. The statement:
For all $m$ greater than or equal to $2$ and for all $n$ greater than or equal to $0$, $m - 1$ divides $m^n - 1$.
Using induction over $n$, the base step comes easy since $m^n - 1$ is $0$ when $n = 0$.
My induction hypothesis is letting $k \geq 0$ and assuming that $m - 1$ divides $m^k - 1$. In order to show that $m - 1$ divides $m^{k+1} - 1$, I obviously need to use the induction hypothesis. However, no matter where I try to use the fact that $m^k - 1 = (m-1)a$ for some $a$ in the integers, the expression $m^{k+1} - 1$ always becomes more difficult to get to $m^{k+1} - 1$ being equal to $(m-1)b$ for some $b$ in the integers.
In other words, I can't figure out any actually helpful way to apply the induction hypothesis with the goal of proving the next step.
Any help would be appreciated!
Answer
Hint:
$$m^{k+1}-1=m^{k+1}-m^k+m^k-1$$
Can you take it from there?
No comments:
Post a Comment