# Given two polynomials $p_1$ and $p_2$, how to define polynomial $p_3$ that has all roots of $p_1$ except those that are $p_2$'s roots?

Hypothesis: all polynomials are define over field $\mathbb{F}_p$, where $p$ is a large prime number.

Consider we have two polynomials, $p_1(x)$ and $p_2(x)$ (as defined above).

For simplicity assume they have some roots in common.

Question: How can we define a polynomial $p_3(x)$ (using $p_1(x)$ and $p_2(x)$) that contains those roots of $p_1(x)$ that are not roots of $p_2(x)$ ?

To be more clear, consider example below:

$p_1(x)=(x-a)\cdot(x-b)$

$p_2(x)=(x-a)\cdot(x-c)$

I need to know how to define $p_3(x)=x-b$, using polynomials $p_1(x)$ and $p_2(x)$

• how about something like $p_3(x)=p_1(x)/\gcd(p_1(x),p_2(x))$? – Anurag A Dec 11 '15 at 10:50
• @AnuragA Thanks – user153465 Dec 11 '15 at 11:09

## 2 Answers

If you can compute the greatest common divisor of two polynomials, then $$p_3(x)=\frac{p_1(x)}{\gcd(p_1(x),p_2(x))},$$ will do the trick. This is always possible over (finite) fields.

• I'd like to ask a separate question: why $a$ is NOT root of polynomials $p(x)=\frac{x-a}{x-b}$, when we define $p(x)$ as above (over a field). But $a$ IS root of the polynomial when it is not defined over the field. – user153465 Dec 11 '15 at 13:13
• I would argue that $a$ is a root of $p(x)=\tfrac{x-a}{x-b}$, but perhaps this is something for a new question. – Servaes Dec 11 '15 at 16:37

HINT:

THe formula given above works say if the roots of $p_1(x)$ are simple ( multiplicity $1$) but may fail otherwise. For example, take $p_1(x)= x^7$, $p_2(x) = x^2$. Hence, we need to eliminate the common roots of $p_1(x)$ and $p_2(x)$ up to the maximum multiplicity of those common roots appearing in $p_1(x)$. To do this we could calculate succesively \begin{eqnarray} q_0(x)& =& p_1(x) \\ q_1(x)& =& \frac{q_0(x)}{ \gcd( q_0(x), p_2(x))}\\ \ldots \\ q_{m}(x)& = &\frac{q_{m-1}(x)}{ \gcd( q_{m-1}(x), p_2(x)) } \end{eqnarray} till the sequence $g_{m}(x)$ stabilizes, that is, till $\gcd (q_m(x), p_2(x) ) = 1$, and take that last $q_m(x)$ as the desired polynomial.