Exploring the Chinese Remainder Theorem for Polynomials: CMI B.Sc. Entrance 2016- Subjective Problem 5

In today's discussion, we delve into a fascinating problem from the 2016 CMI B.Sc. entrance exam that draws on key concepts from number theory, specifically the Chinese Remainder Theorem (CRT), but applies them in the context of polynomials. The problem asks us to find a polynomial $P(x)$ that satisfies two conditions:

• When $P(x)$ is divided by $x^{100}$, the remainder is a constant.
• When $P(x)$ is divided by $(x-2)^3$, the remainder is also a constant.

This setup mirrors the CRT for integers but applies it to the algebraic framework of polynomials.

The video walks through the similarities between integer and polynomial division and emphasizes how techniques like the Euclidean algorithm can be extended to polynomials. Using polynomial differentiation and integration, we solve the given conditions, ultimately arriving at a general form for $P(x)$ by adjusting constants.

A key takeaway is the parallel between solving congruences for integers using the Euclidean algorithm and doing the same for polynomials, underscoring the algebraic unity between these two domains.

Watch the Video

Key Findings and Explanations:

• Chinese Remainder Theorem for Polynomials: The problem presents a polynomial version of the Chinese Remainder Theorem (CRT), requiring the polynomial $P(x)$ to satisfy congruences:

$$
P(x) \equiv 1 \quad\left(\bmod x^{100}\right) \quad \text { and } \quad P(x) \equiv 2 \quad\left(\bmod (x-2)^3\right)
$$

This highlights the deep connection between the two fields.

• Polynomial Division and Remainders: Just like integer division, polynomial division leaves a quotient and remainder. The task is to find a polynomial $P(x)$ that satisfies the given remainder conditions.
• Differentiation and Divisibility: If a polynomial $F(x)$ leaves a constant remainder when divided by $(x-c)^k$, its derivative is divisible by $(x-c)^{k-1}$. For example, the condition:

$$
P^{\prime}(x) \text { must be divisible by } x^{99} \text { and } \quad(x-2)^2
$$

• Integration for Polynomial Construction: Using integration, the form of $P(x)$ is constructed by integrating terms involving $x^{99}(x-2)^2$. This allows for the introduction of constants $a$ and $b$, which are later adjusted based on the remainder conditions:

$$
P(x)=a \cdot \frac{x^{101}}{101}-4 \cdot \frac{x^{100}}{100}+4 \cdot \frac{x^{99}}{99}+b
$$

• Euclidean Algorithm for Polynomials: The Euclidean algorithm, traditionally used for integers, also applies to polynomials. Running the algorithm backwards allows us to solve polynomial congruences in a manner analogous to integer CRT. For instance, finding polynomials $P_1(x)$ and $P_2(x)$ such that:

$$
P_1(x) \cdot x^{100}+P_2(x) \cdot(x-2)^3=1
$$

• Polynomial and Integer Analogy: The parallel between integer and polynomial division is a powerful concept, showing that techniques like the Euclidean algorithm, remainder theorem, and CRT can be seamlessly transferred between these domains.