Let $f(x), g(x)$ be relatively prime polynomial with coefficients in $\mathbb{Z}$. How can I prove that the GCD $(f(n),g(n)) = O(1)$ for $n \to \infty$, $n \in \mathbb{N}$? Thank you for the help!!

  • $\begingroup$ What does GCM mean? $\endgroup$ – bof Mar 13 at 9:44
  • 1
    $\begingroup$ @bof According to Wikipedia, "GCM" is an abbreviation for greatest common measure, which is another term for greatest common divisor. $\endgroup$ – FredH Mar 13 at 9:52

In general, if $A$ is a so-called UFD (unique factorisation domain), then the one indeterminate polynomial ring $A[X]$ will have the same property, so in particular it will be a GCD-ring (i.e. such that any two elements admit a greatest common divisor). If $F$ denotes the fraction field of $A$ and $f, g \in A[X]$ two polynomials, then any greatest common divisor $h$ they have over $A$, it will remain a g.c.d for the pair over $F$; on the other hand, as $F[X]$ is a PID (principal ideal domain), the g.c.d can be expressed as $h=fk+gl$ for $k, l \in F[X]$. In your particular case, it must be that $1=fk+kl$ for $k,l \in \mathbb{Q}[X]$. Clearing denominators, this relation can be brought to the form: $d=fk+gl$, for (a renewed pair of polynomials) $k, l \in \mathbb{Z}[X]$ and $d \in \mathbb{Z}$. From here you can conclude that $(f(n), g(n))\mid d$, for any $n \in \mathbb{Z}$. Now, can you see how this answers your question?


Here's an outline:

  • Use Gauss's Lemma to show that polynomials that are relatively prime over $\mathbb{Z}$ remain relatively prime over $\mathbb{Q}$.

  • Let $p(x)$ and $q(x)$ in $\mathbb{Q}[x]$ be such that $p(x)f(x) + q(x)g(x) = 1$.

  • Clear denominators to get an equation in $\mathbb{Z}[x]$.

  • The conclusion follows.

  • $\begingroup$ What conclusion follows? What does GCM mean? $\endgroup$ – bof Mar 13 at 9:43
  • $\begingroup$ @bof I assumed "GCM" meant "GCD", since he writes $(f(n),g(n))$. The conclusion is that the sequence of GCDs is bounded. $\endgroup$ – FredH Mar 13 at 9:48

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.