# Finding a common factor of two coprime polynomials

I have two coprime univariate integer polynomials. Although they have no common factor as polynomials, they may have common factors at some (integer) values. How can I find such a value?

For example, suppose the polynomials are $x^3-x^2+3x-1$ and $x^3+2$. They are coprime in $\mathbb{Z}[x]$, but $\gcd(27^3-27^2+3\cdot27-1, 27^3+2)=\gcd(19034,19685)=31.$

• How about computing the gcd mod $p$ for various primes. – Michael Burr Dec 15 '15 at 15:42
• @MichaelBurr: Let's say I do that for lots of primes but don't find a common factor. The first number yielding a common root may be very large. – Charles Dec 15 '15 at 15:51

We know that : "two polynomials in $\mathbb{F}[x]$ have a common root (possibly in some field extension of $\mathbb{F}$)" $\Leftrightarrow$ "the resultant of these two polynomials is zero", which implies that for some prime $p$:

"there is a positive integer $n$ such that $\gcd\big(f(n), g(n)\big)=p$" $\Rightarrow$ "the polynomials $f,g$ have a common root $\mod p$" $\Rightarrow$ "their resultant is zero $\mod p$" $\Leftrightarrow$ "their resultant is a multiple of $p$"

(Here, we view the polynomials $f(x)=x^3-x^2+3x-1$, $g(x)=x^3+2$ as polynomials of $\mathbb{Z}_p[x]$)

Thus, it suffices to investigate the prime divisors of the resultant: if $r$ is a divisor of the resultant $Res\big(f,g\big)=k$, then any solution of the simultaneous polynomial equations: $$f(x) \equiv 0 \mod r \\ g(x) \equiv 0 \mod r$$ provides a value of $x=n$ for which: $\gcd\big(f(n),g(n)\big)\geq r>1$.

So, using Mathematica:

In[1]:= Resultant[x^3 - x^2 + 3 x - 1, x^3 + 2, x]

Out[1]= 31

and thus: $$\bigg\{ \begin{array}{c} n^3 - n^2 + 3 n - 1\equiv 0\mod 31 \\ % \\ n^3+2\equiv 0\mod 31 \end{array}\bigg\} \Rightarrow n\equiv27\mod 31$$ Therefore, as user lhf already mentioned in his answer: $\gcd(f(n),g(n))=31$ for all values $n=27+31k$, where $k\geq 0$. For all other values of $n$, $\gcd(f(n),g(n))=1$.

Here is an explanation.

Let $f=x^3-x^2+3x-1$ and $g=x^3+2$.

Even though $\gcd(f,g)=1$ in $\mathbb{Z}[x]$, we cannot write $1=uf+vg$ with $u,v \in \mathbb{Z}[x]$ (because $\mathbb{Z}[x]$ is not a PID). But we can, if we allow $u,v \in \mathbb{Q}[x]$. Indeed, WA tells us that $$1 = \dfrac1{31} (-6 x^2-7 x-3)f(x)+\dfrac1{31}(6 x^2+x+14)g(x)$$ Therefore $$31 = (-6 x^2-7 x-3)f(x)+(6 x^2+x+14)g(x)$$ for all $x \in \mathbb Z$.

This only proves that $\gcd(f(x),g(x))=1$ or $31$ (because $31$ is prime), but it points to $31$.

So we try to solve $f(x)\equiv g(x) \equiv 0 \bmod 31$ and find that $x=27$ is a solution.

Therefore, $\gcd(f(x),g(x))=31$ for all $x=27+31k$. For all other values, $\gcd(f(x),g(x))=1$.