Divisibility Proof with Induction - Stuck on Induction Step

Question

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 1

Hint:

$$m^{k+1}-1=m^{k+1}-m^k+m^k-1$$

Can you take it from there?

Answer 2

It may be of interest to some that the claim in question may be proved by a simple application of double induction where we induct on two variables simultaneously. It is definitely overkill, but I think this proof technique is pretty sexy when it can be applied, and this is certainly one instance. Since using double induction is not too common, I thought I would include a blurb about it from David Gunderson's Handbook of Mathematical Induction before giving the proof.

Blurb: Many mathematical statements involve two (or more) variables, each of which vary independently over, say, $\mathbb{N}$. Some such statements can be proved by induction in different ways. Let $S(m,n)$ be a statement involving two positive integer variables $m$ and $n$. One method to prove $S(m,n)$ for all $m\geq 1$ and $n\geq 1$ is to first prove $S(1,1)$, then by induction prove $S(m,1)$ for each $m$, and then for each fixed $m_0$, inductively prove $S(m_0,n)$ for all $n$. [ p. 44]

---

Problem: Show that $S(m,n)$ is true where $$ S(m,n) : (\forall m\in\mathbb{Z^+}\setminus\{1\})(\forall n\in\mathbb{Z^+}\cup\{0\})[(m-1)\mid (m^n-1)]. $$

Proof. First we prove that $S(m,0)$ is true for all $m\geq 2$.

Base step: The statement $S(2,0)$ is true since $(2-1)\mid (2^0-1)$.

Inductive step (inducting on $m$): For some $k\geq 2$, assume that $S(k,0)$ is true; that is, $(k-1)\mid (k^0-1)$. Since $((k+1)-1)\mid ((k+1)^0-1)$ is clearly true for all $k\geq 2$, we can see that $S(k,0)\to S(k+1,0)$, and by mathematical induction, for all $m\geq 2, S(m,0)$ is true.

Now fix an arbitrary $m_0$. Then $S(m_0,0)$ is true and so this is a base step for proving that for all $n, S(m_0,n)$ holds.

Inductive step (inducting on $n$): This step is of the form $S(m_0,\ell)\to S(m_0,\ell+1)$. Let $\ell\geq 0$ be fixed and assume that $S(m_0,\ell)$ is true, that is, $(m_0-1)\mid (m_0^\ell-1)$. Starting with the right-hand side of $S(m_0,\ell+1)$, \begin{align} m_0^{\ell+1}-1 &=m_0(m_0^\ell-1)+(m_0-1)\\[0.5em] &=m_0[\eta(m_0-1)]+(m_0-1)\tag{by $S(m_0,\ell);\eta\in\Bbb{Z}$}\\[0.5em] &=(\eta m_0+1)(m_0-1)\tag{factor}\\[0.5em] &=\gamma(m_0-1),\tag{$\gamma=\eta m_0+1$} \end{align} which is a multiple of the left-hand side of $S(m_0,\ell+1)$, where $\gamma=\eta m_0+1$ and $\gamma\in\Bbb{Z}$ since $1,\eta,m_0\in\Bbb{Z}$ (closure of addition and multiplication in $\Bbb{Z}$). Since $m_0^{\ell+1}-1=\gamma(m_0-1)$, we can see that, by definition, $(m_0-1)\mid (m_0^{\ell+1}-1)$; hence, by induction, for each fixed $m_0$ and $n\geq 0, S(m_0,n)$ is true, completing the inductive step.

Since $m_0$ was arbitrary, by induction, for all $m\geq 2$ and $n\geq 0$ the statement $S(m,n)$ is proved. $\Box$