# Chinese remainder Theorem in polynomials in one variable.

In a question I was answering, I needed to solve these congruences to proceed, and find the least $$k<1000$$

$$2k+k^2 = 0 \pmod 3$$

$$2k^3 + 6k = 0 \pmod 7$$

$$k = 0 \pmod 2$$

My try:

due to the third statement

$$k = 2j$$ for some integer $$j$$,

due to the second statement $$k = 7x ; k= 7x+2$$ for some integer $$k$$

due to the first statement

$$k = 3y+1; k = 3y$$

can I just exhaust all of the $$4$$ possible cases due to these statements and use the Chinese remainder theorem? I don't know if I'm doing it right or not.

• The solutions to $2 k^3 + 6 k \equiv 0 \bmod 7$ are $k \equiv 0, 2$ and $5 \bmod 7$. Yes, in each case you want to use Chinese remainder theorem. Mar 12 '19 at 12:28
• Is it really "least positive $k$" as the condition? Mar 12 '19 at 12:39

As pointed out in the comments, the solutions for the second congruence are $$k\equiv0,2,5\bmod7$$. Now combine the congruences one-by-one: the first and third give $$k\equiv0,4\bmod6$$, which when combined with the second gives $$k\equiv0,12,16,28,30,40\bmod42$$ So the least positive $$k$$ is $$12$$, and the greatest $$k<1000$$ is $$996$$.

$$\bmod 2\!:\,\ k\equiv 0\ \$$ (so the summand for this in the CRT formula will be $$0$$ and can be ignored)

$$\bmod 3\!:\,\ 0 \equiv k(k+2)\iff \color{#0a0}{k\equiv 0,1},\,$$ call them $$\,\color{#0a0}{k \equiv a}$$

$$\bmod 7\!:\,\ 0\equiv k(2k^2-1)\iff \,k\equiv\color{#c00} 0\,$$ or $$\,k^2\equiv 1/2\equiv 8/2\iff k\equiv \color{#c00}{\pm 2},\,$$ call them $$\,k\equiv\color{#c00} b$$

By  CRT: \,\ \begin{align}&k\equiv 0\!\!\!\pmod{\!2}\\&k\equiv \color{#0a0}a\!\!\!\pmod{\!3}\\&k\equiv \color{#c00}b\!\!\!\pmod{7}\end{align}\iff k \equiv -14\,\color{#0a0} a - 6\,\color{#c00} b\pmod{\!42}\

Next we need to substitute all possible values of $$a,b$$ into the above CRT formula.

So $$\ \ \ \color{#0a0}{a\equiv 0}\,\Rightarrow\, k \equiv -6\,\color{#c00}b \equiv -6[\color{#c00}{0,-2,2}]\equiv 0,12,30\,\pmod{\!42}$$

and $$\,\color{#0a0}{a\equiv 1}\,\Rightarrow\, k\,\equiv\, -14-6b\, \equiv\, -14\,+\, [0,12,30]\equiv 28,40,16$$

Least non-negative $$k$$ is $$0$$. If you are looking for non-zero solutions then, essentially $$k = 2j$$; $$j = 7i+1, 7i-1$$ or $$7i$$; $$i = 3b, 3b+1$$;