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.

  • 1
    $\begingroup$ Corrected your latex issues.. $\endgroup$ – 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.

It happens to be that this Euclidean algorithm and back-substitution is gross, and I wouldn't recommend doing it by hand. But you can see the actual result using Wolfram|Alpha's implementation.


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.