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!
Best Answer
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$