# Prove that $n^3+5n$ is always divisible by 6 using induction with mod

So I had to prove this in my calculus exam today

Prove that $$n^3+5n$$ is always divisible by 6.

I know that there have been other people around here having asked this already, but I chose a different approach and would really appreciate to hear whether my train of thought here was right or wrong. So I am especially not looking for the "right way" to prove it (i.e., I don't need a proper solution) I would just appreciate for somebody to assess my solution, if it's completely wrong or possibly not complete etc.

so, what I did:

Initial case prove that $$n^3+5n \bmod 6 = 0$$ for $$n=1$$. $$1^3+5\cdot 1 \bmod 6 = 0 \Leftrightarrow 6 \bmod 6 = 0$$ which is trivially true.

Induction step Prove that for every $$n$$, if the statement holds for $$n$$, then it holds for $$n + 1$$. $$((n+1)^3+5(n+1)) \bmod 6 =0 \\ \Leftrightarrow ((n^3+3n^2+3n+1)+5n+5) \bmod 6 =0 \\ \Leftrightarrow (n^3+5n \bmod 6) + (3n^2+3n+6 \bmod 6)=0 \\ \Leftrightarrow 0+(3n^2+3n+6 \bmod 6)=0 \\ \Leftrightarrow 3n^2+3n+6 \bmod 6 =0.$$

And this is true for all $$n \in \mathbb{N}$$, where from the third to the fourth line, we replaced with the induction hypothesis that $$n^3+5n \bmod 6 =0$$ . Take for instance $$1, 2,3,...$$ it is always divisible by 6 without leaving any rest!!

However, my other friends that took the exam said that this is in need of some extension to show that the last line actually holds true for whatever n you insert. But I cannot grasp what they mean; by the definition of the modulus, it should already trivially be given that the last line is right...

I'm really looking forward to your thoughts, do you think I would at least get partial points for this? :( I really don't see how this can be wrong...

Thanks so much, Lin

• You just need to show that $2\mid n(n+1)$, then it follows that $6\mid 3n^2+3n+6$. This is certainly only a partial loss of points. Mar 11, 2021 at 12:43
• Yes, it is "in principle" right. I would give full points for some of the solutions here, and less points for you, because your solution is a bit too long and not every step is clear. Have a look at the duplicate yourself! Mar 11, 2021 at 12:45
• Please, see the edits I did to your post so you learn how to use better mathjax. Mar 11, 2021 at 12:47
• Bitte schön, you are welcome! This site has good solutions, and sometimes this helps to improve the own solution a bit. And the advantage is, you can do this on your own. Mar 11, 2021 at 12:51
• BTW, a simpler way to solve this is to see that $$n^3+5n \equiv n^3-n = (n-1)n(n+1)\pmod 6$$, and of course both $2$ & $3$ must divide $(n-1)n(n+1)$. Mar 11, 2021 at 13:11

In view of the final step, $$3n^2+3n+6\equiv 0\mod 6$$ is equivalent to $$3n^2+3n\equiv 0\mod 6$$, i.e.,

$$3(n^2+n)\equiv 0\mod 6$$.

So it is sufficient to show that

$$2\mid n^2+n$$.

But $$n^2+n = n(n+1)$$ is a product of consecutive integers and one of which will be even. Thus $$n^2+n$$ is a multiple of $$2$$ and hence $$3(n^2+n)$$ is a multiple of $$6$$, as required.

• So you also agree that my induction is right, and only the part you mention is missing? :) Mar 11, 2021 at 12:47

Your friends are right. You need to explain why the last equivalent equation is an identity, meaning it solves for any integer n greater than zero.

To do that you show that $$3n^2+3n+6$$ is divisible both by 2 and 3. Divisibility by 3 is obvious since the expression is a multiple of 3. You show that by rewriting the expression into $$3(n^2+n+2)$$ Divisibility by 2 results from observing that the product $$n(n+1)$$ of two consecutive numbers is always an even number: $$n^2+n+2=n(n+1)+2=2k\cdot(2k\pm1) +2=2[k(2k\pm1)]$$

• Thanks! But just for the fun of it, out of 12 points in total, how many would you give me for my solution? xP Mar 11, 2021 at 13:02
• Is arguable since you failed to finish to prove p(n)->p(n+1). I guess you could loose 1 or 2p depending on how you presented the induction method. p(1) true and p(n)->p(n+1) then p(n) true for n>0. Depends on the teacher. Mar 11, 2021 at 13:10
• yeyyyyy! that is enough excitement for me :D Mar 11, 2021 at 13:11

This is correct, but as your friends said, not proving the last line may cause some loss of points. To prove this, it's not very "long" or something. Just show that $$3n^2+3n+6\equiv 0\ (\textrm{mod}\ 2)$$ Since it is trivial that it is $$0\ \textrm{mod}\ 3$$, the statement follows.

Hope this helps. Ask anything if not clear :)

• Thanks so much to you too!! Mar 11, 2021 at 12:48
• Thanks @LinShao, but one more thing: accept either my or the other answer here just to ensure that this is answered. Mar 11, 2021 at 12:50

Since your final step implies $$3\mid 3n^2-3n$$, it suffices to show $$2\mid n^2-n$$ for any $$n$$, which can be seen as trivial. That was all you missed in my opinion.

• Thanks for also giving me hope :) After all I'm not a total idiot in math, it seems xD Mar 11, 2021 at 13:36