2
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ NP: this is a good answer: short and elegant! $\endgroup$ – awllower Aug 25 '13 at 4:57
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If one already knows about Chinese-Remainder theorem, my last step is redundant indeed. $\endgroup$ – awllower Aug 25 '13 at 7:16

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.