# Problem related to remainder

A polynomial in $x$ leaves a remainder $2$ and $3$ when divided by $x-1$ and $x+1$. What is the remainder, when divided by $x^2-1$ ?

• hint: $(x-1)(x+1) = x^2-1$ – Mathias711 Apr 24 '14 at 9:55

Hint. The remainder will be a linear polynomial, say $ax+b$, and you need to determine $a$ and $b$. The division can be written as $$f(x)=(x^2-1)q(x)+ax+b\ .$$ From the given information you have $$f(x)=(x-1)r(x)+2\ .$$ Now substituting $x=1$ in these two equations will give some information about $a$ and $b$, and you can use the other given remainder in a similar way to get a second equation. You can then solve for $a$ and $b$.

Though it can be done by (Lagrange) interpolation, it is just as simple (and more powerful) to use the Chinese Remainder Theorem (CRT), which is $\color{#c00}{\rm very\ easy}$ when the $\color{#c00}{\rm Bezout}$ identity is known

By CRT,  if $\ \color{#c00}{j g} + \color{#c00}{k h} = 1\,$ then $\ \begin{eqnarray}f\equiv a\!\!\!\pmod g\\f\equiv b\!\!\!\pmod h\end{eqnarray}$ $\!\iff\!\!$ $\begin{eqnarray} f&\equiv&\ a\,\color{#c00}{kh}\, +\, b\,\color{#c00}{jg}&&({\rm mod}\ {gh})\\ &\equiv& a+(b\!-\!a)\color{#c00}{jg}&&({\rm mod}\ gh)\end{eqnarray}$

Hence $\ \frac{1}{2} \underbrace{(x\!+\!1)}_{\large g}-\frac{1}2\underbrace{(x\!-\!1)}_{\large h} = 1\,$ and $\,\ a,b = 3,2\ \Rightarrow\ f\equiv 3-\color{#c00}{\frac{1}2(x\!+\!1)} \pmod{\!\!x^2\!-\!1}$

Remark $\$ It was $\,\color{#c00}{\rm easy}$ here since $\,\ g\ {\rm mod}\ h = g - h = (x\!+\!1)-(x\!-\!1) = 2\$ is invertible in $\,\Bbb Q\,$ hence scaling by $\,1/2\,$ yields the Bezout identity, which immediately yields the solution as above. Generally it is just as easy when $\ g\ {\rm mod}\ h\$ is invertible (which is equivalent to the extended Euclidean algorithm (EEA) terminating in $1$ step, i.e. this is an optimization of the EEA). In particular, the EEA terminates in one step if one of the polynomials is linear.

Since Lagrange interpolation is the special case of CRT when both moduli are linear polynomials, the above optimization always applies.

Let $\displaystyle f(x)=(x^2-1)g(x)+A(x-1)+B(x+1)$ where $g(x)$ is a polynomial and $A,B$ are constants

Using Polynomial remainder theorem, $\displaystyle2=f(1)=B\cdot(1+1)\iff B=1$

Similarly, $\displaystyle3=f(-1)=A(-1-1)\iff A=?$

• You should justify why there exists such a representation of $f\ \$ – Bill Dubuque Apr 24 '14 at 18:40
• @BillDubuque, Because the remainder by a Quadratic Polynomial will be a linear Polynomial $$A(x-1)+B(x+1)=x(A+B)+B-A=x a+b$$ – lab bhattacharjee Apr 25 '14 at 2:01
• You need more, i.e. generally it is not true that if $\,f_1,f_2\,$ are polynomials of degree $\,1\,$ then every polynomial of degree $\le 1$ has form $\, A f_1 + B f_2,\,$ e.g. it is false if $\,f_1 = C f_2.\$ – Bill Dubuque Apr 25 '14 at 2:18
• @BillDubuque, Here $a,b$ are constants may be zero, too. I should written : "will be at most a linear Polynomial" – lab bhattacharjee Apr 25 '14 at 2:20
• Yes, I know $A,B$ are constants. That doesn't fix it, see the mentioned counterexample. – Bill Dubuque Apr 25 '14 at 2:21