1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Daniel W. Farlow Feb 3 '15 at 23:00
3
$\begingroup$

Hint:

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

Can you take it from there?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Daniel W. Farlow Feb 3 '15 at 0:50
  • $\begingroup$ 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! $\endgroup$ – Anthony Feb 3 '15 at 0:52
  • $\begingroup$ @induktio, sounds like overkill to me. You really only need to induct on $n$. $\endgroup$ – Barry Cipra Feb 3 '15 at 0:53
  • $\begingroup$ @BarryCipra I think my question was more rhetorical than anything haha--it has to be overkill. Would make for a sexy solution\proof though. $\endgroup$ – Daniel W. Farlow Feb 3 '15 at 0:54
  • $\begingroup$ @induktio, actually, you've got me wondering now how the proof might go if you induct on $m$ instead of $n$.... $\endgroup$ – Barry Cipra Feb 3 '15 at 0:58
4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thank you, this is very helpful. I've always found simple induction on multiple variable problems confusing. $\endgroup$ – jeremy radcliff Jan 17 '17 at 23:58
  • $\begingroup$ @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! $\endgroup$ – Daniel W. Farlow Jan 18 '17 at 1:42

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.