# Congruence Equation $3n^3+12n^2+13n+2\equiv0,\pmod{2\times3\times5}$

How to solve the following congruence equation? $$3n^3+12n^2+13n+2\equiv0,\pmod{2\times3\times5}$$ If $t_n$ be the $n$th triangular number, then $$t_1^2+t_2^2+...+t_n^2=\frac{t_n(3n^3+12n^2+13n+2)}{30}$$ so if we solve this congruence equation we find the values of $n$ that $t_n$ divides $t_1^2+t_2^2+...+t_n^2$.

Work first modulo $2$. We can rewrite the congruence as $n^3+n\equiv 0\pmod{2}$. Note that this always holds.

Now work modulo $3$. The congruence can be rewritten as $n+2\equiv 0\pmod{3}$. This holds precisely if $n\equiv 1\pmod{3}$.

Finally, work modulo $5$. The congruence can be rewritten as $3n^3-3n^2+3n-3\equiv 0\pmod{5}$, and then as $(n-1)(n^2+1)\equiv 0\pmod{5}$. This has the solutions $n\equiv 1\pmod{5}$, $n\equiv 2\pmod{5}$ and $n\equiv 3\pmod{5}$.

So the conditions come down to $n\equiv 1\pmod{3}$ and $n\equiv 1$, $2$, or $3$ modulo $5$.

The solutions are therefore $n\equiv 1$, $n\equiv 7$ and $n\equiv 13\pmod{15}$.

• NP: this is a good answer: short and elegant! – awllower Aug 25 '13 at 4:57

We solve it by looking at different primes one at a time:
modulo 2:
The equation becomes $0\equiv0\pmod2$, since $x^n\equiv x\pmod2$ for every integer $x\gt0$. Hence this is always true.
modulo 3:
We obtain now: $n+2\equiv0\pmod3$, i.e. $n\equiv1\pmod3$.
modulo 5:
The equation is seen to be $(1+n^2)(3n+2)\equiv0\pmod5,$ hence $\begin{cases}n^2\equiv4\pmod5&\text{or}\\n\equiv1\pmod5\end{cases}.$ Thus the solution is $n\equiv1, 2, -2\pmod5.$
To sum up, we only have to solve for the set of congruence equations: $$\begin{cases}n\equiv1\pmod3\\n\equiv1, 2, -2\pmod5\end{cases}.$$
We find the solution by noticing that $$\begin{cases}6\equiv0\pmod3&10\equiv1\pmod3\\6\equiv1\pmod5&10\equiv0\pmod5\end{cases}.$$
Consequently, the solutions are the linear combinations: $n\equiv10+6a\pmod{15},$ where $a=1, 2, -2.$ Namely, $$n\equiv1, 7, 13\pmod{15}.$$
Hope this helps.

• If one already knows about Chinese-Remainder theorem, my last step is redundant indeed. – awllower Aug 25 '13 at 7:16