# Exercise on polynomial and GCD

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!!

• What does GCM mean? – bof Mar 13 at 9:44
• @bof According to Wikipedia, "GCM" is an abbreviation for greatest common measure, which is another term for greatest common divisor. – 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.

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