The Greatest Common Divisor of Polynomials over a Field

# The Greatest Common Divisor of Polynomials over a Field

Recall that if $a$ and $b$ are positive integers then the greatest common divisor $\gcd (a, b)$ is defined as a positive integer $d$ such that $d | a$ and $d | b$ and if $c$ is any other common divisor of $a$ and $b$ then $c | d$.

We now make an analogous definition for the greatest common divisor of two polynomials over a field.

 Definition: Let $(F, +, \cdot)$ be a field and let $f, g \in F[x]$. The Greatest Common Divisor of $f$ and $g$ is a polynomial $d \in F[x]$ denoted $\gcd (f, g) = d$ if the polynomial $d$ satisfies the following properties: 1) $d$ is a monic polynomial. 2) $d(x) | f(x)$ and $d(x) | g(x)$ ($d$ is a common factor of $f$ and $g$). 3) If $h \in F[x]$ is such that $h(x) | f(x)$ and $h(x) | g(x)$ then $h(x) | d(x)$ (Every other common factor of $f$ and $g$ is a common factor of $d$). We say that $\gcd (0, 0)$ does not exist.
 Definition: Let $(F, +, \cdot)$ be a field and let $f, g \in F[x]$. $f$ and $g$ are said to be Relatively Prime or Coprime if $\gcd(f, g) = 1$.

For example, consider the field of real numbers and the following polynomials:

(1)
\begin{align} \quad f(x) = x^2 -2x + 1 \\ \quad g(x) = x^2 - 1 \end{align}

Note that $(x - 1) | f(x)$ and $(x - 1) | g(x)$. Furthermore, $(x - 1)$ is a monic polynomial and any other divisor of $f$ and $g$ is a divisor of $(x - 1)$. Therefore:

(2)
\begin{align} \quad \gcd (x^2 -2x + 1, x^2 - 1) = x - 1 \end{align}

We now look at an important theorem which allows us to write the greatest common divisor of two polynomials $f$ and $g$ in a special form.

 Theorem 1: Let $(F, +, \cdot)$ be a field and let $f, g \in F[x]$ with $f(x) \neq 0$ and $g(x) \neq 0$. Then there exists polynomials $a, b \in F[x]$ such that if $\gcd (f, g) = d$ then $d(x) = a(x)f(x) + b(x)g(x)$.
• Proof: Let $f, g \in F[x]$ with $f(x) \neq 0$ and $g(x) \neq 0$. Consider the following set of polynomials over $F$:
(3)
\begin{align} \quad I = \{ a(x)f(x) + b(x)g(x) : a, b \in F[x] \} \end{align}
• Note that $I$ contains a nonzero polynomial. Furthermore, it's easy to see that if $s, t \in I$ then $(s + t) \in I$, and is $s \in I$ and $q \in F[x]$ then $(s \cdot q) \in I$. So from the theorem on the Ideals in the Set of Polynomials over a Field page, there exists a polynomial $d \in I$ with $d(x) \neq 0$ of minimal degree in $I$ such that:
(4)
\begin{align} \quad I = \{ q(x)d(x) : q \in F[x] \} \end{align}
• So let $f, g \in I$. Then there exists $q_1, q_2 \in F[x]$ such that $f(x) = q_1(x)d(x)$ and $g(x) = q_2(x)d(x)$. So $d(x) | f(x)$ and $d(x) | g(x)$ so $d$ is a common factor of $a$ and $b$. So since $d \in I$ there exists polynomials $a, b \in F[x]$ such that:
(5)
\begin{align} \quad d(x) = a(x)f(x) + b(x)g(x) \end{align}
• If $h \in F[x]$ is any polynomial that is a common factor of $f$ and $g$ we must have that $h(x) | d(x)$. So $\gcd (f, g) = d$ as well. $\blacksquare$
 Theorem 2: Let $(F, +, \cdot)$ be a field and let $f, g, p \in F[x]$. If $\gcd (f, p) = 1$ and $p(x) | f(x)g(x)$ then $p(x) | g(x)$.
• Proof: Since $\gcd (f, p) = 1$, by the previous theorem there exists polynomials $a, b \in F[x]$ such that:
(6)
\begin{align} \quad 1 = a(x)f(x) + b(x)p(x) \end{align}
• Multiply both sides by $g(x)$ to get:
(7)
\begin{align} \quad g(x) = a(x)f(x)g(x) + b(x)p(x)g(x) \end{align}
• Since [$p(x) | f(x)g(x)$ we have that $p(x) | a(x)f(x)g(x)$. Also $p(x) | b(x)p(x)g(x)$. So $p(x) | g(x)$. $\blacksquare$
 Theorem 3 (The Euclidean Algorithm): Let $(F, +, \cdot)$ be a field and let $f, g \in F[x]$ with $g(x) \neq 0$. Then if $q, r \in F[x]$ are the unique polynomials from the Division algorithm such that $f(x) = g(x)q(x) + r(x)$ where $r(x) = 0$ or $\deg (r) < \deg (g)$ then: 1) If $r(x) = 0$ with $g(x) = a_0 + a_1x + ... + a_mx^m$ then $\displaystyle{\gcd (f, g) = \frac{1}{a_m} g(x)}$. 2) If $r(x) \neq 0$ then $\gcd (f, g) = \gcd (g, r)$.