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

  • $\begingroup$ How about computing the gcd mod $p$ for various primes. $\endgroup$ – Michael Burr Dec 15 '15 at 15:42
  • 1
    $\begingroup$ @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. $\endgroup$ – 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$.


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.