# Divisibility Proof with Induction - Stuck on Induction Step

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!

• It should probably be noted that this question is really a disguised duplicate (probably unintentional) of this question. Showing that $(m-1)\mid (m^n-1)$ is really equivalent to showing that $m-1$ is always a factor of $m^n-1$, just as the question linked to considers. – Daniel W. Farlow Feb 3 '15 at 23:00

Hint:

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

Can you take it from there?

• I haven't really attempted the problem at all, but doesn't this look like a good problem for some double induction? Or you think that might be overkill? – Daniel W. Farlow Feb 3 '15 at 0:50
• Normally the process of typing the question out on this site gives me some magical intuition as to what I'm missing but I couldn't get it this time. That definitely gives me what I needed, I'm rusty if I can't remember to try adding 0 everywhere and expanding it when I'm stuck! Thanks for the help! – Anthony Feb 3 '15 at 0:52
• @induktio, sounds like overkill to me. You really only need to induct on $n$. – Barry Cipra Feb 3 '15 at 0:53
• @BarryCipra I think my question was more rhetorical than anything haha--it has to be overkill. Would make for a sexy solution\proof though. – Daniel W. Farlow Feb 3 '15 at 0:54
• @induktio, actually, you've got me wondering now how the proof might go if you induct on $m$ instead of $n$.... – Barry Cipra Feb 3 '15 at 0:58

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$

• Thank you, this is very helpful. I've always found simple induction on multiple variable problems confusing. – jeremy radcliff Jan 17 '17 at 23:58
• @jeremyradcliff Thanks for mentioning that it helped! Glad to hear that--haven't heard much in the line of praise or criticism concerning arguments using double induction. Thought it might be nice to point it out here even though it's really not necessary--glad it helped! – Daniel W. Farlow Jan 18 '17 at 1:42