Prove by induction that for $m, n ∈ N$, $m^{2n+1} − m$ is divisible by $6.$

What I have thus far:

Base case: $m=n=0$; $0^{0+1}-0 = 0$, which is divisible by $6$.

Base case(2): $m=n=1$; $1^{2+1}-1 = 0$, which is divisible by $6$.

Proposition: $m^{2n+1} − m = 6 \times k$ for $m,n ∈ N$.

Induction step: $m^{2n+1} − m$ => $m^{2(n+1)+1} -m$

And this is where I'm kinda stuck on.

I was also wondering if there maybe was an easier way to prove this by using $m^{2n+1} − m \mod 6 = 0$ as proposition.

  • $\begingroup$ Did you check if it's true for $m=n=1$? $\endgroup$ May 2 at 16:48
  • $\begingroup$ "$m^{2n}+1 − m = m^{2n}+1 − m$" Well, yeah... everything is equal to itself.... "$m^{2n}+1 − m=(6k+m)∗m−m$". Uh... no it doesn't. You just said $m^{2n} + 1-m = 6k$.... Did you mean $m^{2(n+1)} + 1 - m = m^{2n}m^2 + 1-m$ which .... doesn't seem to be going where you are heading. $\endgroup$
    – fleablood
    May 2 at 16:53

Your induction step isn't right

$m^{2(n+1) + 1} - m = m^{2^n+1}m^2 - m=$

$([m^{2n+1} -m] + m)m^2 - m = $

$(6k + m)m^2 - m =$

$6km^2 + m^3- m$.

So we must prove $m^3 -m$ is always a multiple of $6$.

Hint: $m^3 - m = m(m^2-1) = m(m-1)(m+1)$


In general you can do two proofs by induction, one where one variable is is fixed and the other is run through in the proof.

That is to say. Prove for a fixed $m$ that Base case $m^{2*0+1} - m$ is divisible by $6$; and induction step if $m^{2n+1} - m$ is divisible by $6$ then $m^{2(n+1) + 1} -m$ is divisible by $6$; ANd then to a second indcution proof for a fixed $n$ that Base case $0^{2n+1} - 0$ is divisble by $6$; and induction step if $m^{2n+1} - m$ is divisble by $6$ then $(m+1)^{2n+1} -(m+1)$ is divisible by $6$.

In this case it's not so straight forward. The induction on $n$ with $m$ fix will rely on us showing $m^3 - m$ is divisible but $6$. And the induction on $m$ with $n$ fix will rely on showing $\sum_{k=1}^{2n} (-1)^k{2n+1\choose k}m^k$ is divisible by $6$.

But I think the easiest thing is to first prove that $m^2 -m$ is divisible by $6$. This can be done by induction but it is easier to do it by modular arithmentic $\mod 2$ and $\mod 3$.

$m^3 -m = (m-1)m(m+1)$ so if $m\equiv 0,1,-1\pmod 3$ then $m,m-1,m+1 \equiv 0 \pmod 3$ so $3|(m-1)m(m+1)$ and if $m \equiv 0,1 \pmod 2$ then $m,m-1\equiv 0\pmod 2$ so $2|(m-1)m(m+1)$ and so $6|(m-1)m(m+1)$.

Then prove by induction for a fixed $m$ than induction on $n$ shows $6|m^{2m+1} - m$.


Or to use modular arithmetic from the start.

$m^{2m+1} - m = m(m^{2n} - 1)$.

If $m\not \equiv 0 \pmod{2,3}$ its easy to show therefore than $m^2\equiv 1\pmod {2,3}$ and therefore $m^{2n} \equiv 1 \pmod{2,3}$ and if $2,3 \not \mid m$ then $2,3 \mid m^{2n} -1$ so either way $6|m(m^{2n} -1)$

i.e. either $m \equiv 0 \pmod 2$ or if $m\not \equiv 0\pmod 2$ then $m^2\equiv 1 \pmod 2$.

And either $m \equiv 0 \pmod 3$ or if $m\not \equiv 0 \pmod 3$ then $m^2 \equiv 1\pmod 3$.


In hindsight, I think the easiest answer should have been: It's often easiest to prove things are divisible by $2$ and by $3$ separately.

It's easy to convince ourselves that $m$ and $m^{2n}$ must be both even or both odd so $m^{2n} -m$ must be even. ($m\equiv 0, 1\pmod 2$ and $m^k\equiv 0^k, 1^k\equiv 0, 1\equiv m\pmod 2$ so $m^k-m \equiv m-m\equiv 0 \pmod 2$.) And it's not not much harder to convince ourselves that similarly that $m^2 \equiv \begin{cases} 0&m\equiv 0 \pmod 3\\1&m\equiv 1\pmod 3\\1&m\equiv 2\pmod 3\end{cases}\pmod 3$ so $m^{2k+1}=(m^2)^k m \equiv \begin{cases}0\cdot m =0\equiv m&m\equiv 0 \pmod 3\\1\cdot m \equiv m&\begin{cases}1\\2\end{cases}\pmod 3\end{cases}\equiv m \pmod 3$. So $m^{2n+1} - m\equiv m-m\equiv 0 \pmod 3$.

And that would be all.


$m^{2n+1}-m=m(m^{2n}-1)\equiv0\pmod2$, because either $m\equiv0\bmod2$,

or $m\equiv1\bmod2$, in which case $m^{2n}-1\equiv0\pmod 2.$

$m^{2n+1}-m=m(m^{2n}-1)\equiv0\pmod3$, because either $m\equiv0\bmod3$,

or $m\equiv\pm1\pmod3$, in which case $m^{2n}-1\equiv 0\pmod3$.

To prove it by induction, note that $m^{2n+3}-m=m^{2n+1}(m^2-1)+m^{2n+1}-m$

$=m^{2n}m(m+1)(m-1)+(m^{2n+1}-m)$; can you see that's divisible by $2$ and $3$?


Base case:


which is true because both $2$ and $3$ divide $(m-1)m(m+1)$.

Inductive step:

Assume $m^{2n+1}-m\equiv0\pmod6$.

Then $m^{2n+1}\equiv m\pmod6$

Multiply both sides by $m^2$:

$m^{2n+3}\equiv m^3\equiv m\pmod6$

by re-applying the base case.


The method of induction is written in the other answer. I provide an alternate answer.

Observe that:

$$\begin{align}\frac{m^{2n+1}-m}{m(m^2-1)}&=\frac{m(m^{2n}-1)}{m(m^2-1)}\\ &=\frac{m\left(\left(m^{2}\right)^n-1^n\right)}{m(m^2-1)}\\ &=\frac{m\left(\left(m^{2}\right)^n-1^n\right)}{(m-1)m(m+1)} \\ &\in\mathbb Z.\end{align}$$

It is well-known that, $(m-1)m(m+1)\equiv 0 ~(\text{mod}~6).$


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.