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

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.

• Did you check if it's true for $m=n=1$? May 2 at 16:48
• "$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. May 2 at 16:53

$$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:

$$m^3-m\equiv0\pmod6$$

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).$$