# chinese remainder theorem for polynomials

Find a polynomial $$p(x)$$ that simultaneously has both the following properties. $$(i)$$ When $$p(x)$$ is divided by $$x^{100}$$ the remainder is the constant polynomial $$1.$$ $$(ii)$$ When $$p(x)$$ is divided by $$(x-2)^3$$ the remainder is the constant polynomial $$2.$$

Though I could find the polynomial by taking derivative (works better because the remainders are simple),I wanted to understand how CRT gives the polynomial.

The solution states the following: $$x^{100}$$ and $$(x − 2)^3$$ do not share a common factor, you know without any work that a polynomial with given properties must exist. The same Euclidean algorithm (but now with polynomials) gives a systematic way to find it. In the given problem we could use a different trick because the specified remainders here were rather simple (constants).But there is a conceptual way as well by implementing the Chinese remainder theorem.

I am new and poor with Latex.And thank you in advance.

• Corrected your latex issues.. – Stranger Forever May 28 '20 at 18:35

We are given the system $$\begin{cases} p(x) \equiv 1 \mod{x^{100}} \\ p(x) \equiv 2 \mod{(x-2)^3}. \end{cases}$$ The first line indicates that $$p(x) = 1 + g(x) x^{100}$$ for some polynomial $g(x)$. Inserting into the second line gives that $$1 + g(x) x^{100} = 2 \mod (x-2)^3,$$ or rather that $$g(x) x^{100} + h(x) (x-2)^3 = 1$$ for some polynomials $g(x)$ and $h(x)$. This equation has a solution since $x^{100}$ and $(x-2)^3$ are relatively prime. Note that this is very similar to questions looking like $$3x + 5y = 1,$$ or more generally $$ax + by = 1,$$ which are traditionally solved using the Euclidean algorithm and back-substitution.