0
$\begingroup$

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)$

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user153465 Dec 11 '15 at 13:13
  • $\begingroup$ 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. $\endgroup$ – Servaes Dec 11 '15 at 16:37
2
$\begingroup$

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.

$\endgroup$

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.