Limited access

Upgrade to access all content for this subject

The Euclidean Algorithm for Polynomials is a way to find the greatest common divisor of two polynomials by repetitive usage of the division algorithm. Let $f(x), g(x) \in F[x]$, where $F$ is a field. Let $\text{deg}(h(x))$ denote the degree of $h(x)$, which is the number of the largest exponent of $x$ that is seen with a nonzero coefficient (e.g. $\text{deg}(x^2 + x + 1) = 2$ and $\text{deg}(5) = 0$). Then, we get the following sequence of quotients and remainders:

$$\begin{align*} f(x) &= q_0(x) g(x) + r_0(x)\qquad(\text{deg}(g(x)) > \text{deg}(r_0(x)))\\\ g(x) &= q_1(x) r_0(x) + r_1(x) \qquad (\text{deg}(r_0(x)) > \text{deg}(r_1(x))) \\\ r_0(x) &= q_2(x) r_1(x) + r_2(x) \qquad (\text{deg}(r_1(x)) > \text{deg}(r_2(x)))\\\ &\vdots\\\ r_{m - 2}(x) &= q_m(x) r_{m - 1}(x) + r_m(x) \qquad (\text{deg}(r_{m - 1}(x)) > \text{deg}(r_m(x)))\\\ r_{m - 1}(x) &= q_{m + 1}(x) r_{m}(x)\end{align*}$$

...where $r_m(x)$ is the final nonzero remainder. Note that up to a constant $\gcd(f(x), g(x)) = r_m(x)$, which means we are on the right track, but need to keep the following in mind with respect to the definition of the greatest common divisor of two polynomials.

Recall that if $f_1(x)$ and $f_2(x)$ are two nonzero polynomials in $F[x]$ (where $F$ is a field) that then there is a nonzero monic polynomial (the coefficient of the highest degree is $1$) $f_3(x)$ of largest degree such that $f_3(x)$ divides $f_1(x)$ and $f_2(x)$. The polynomial $f_3(x)$ is unique and we say that $\gcd(f_1(x), f_2(x)) = f_3(x)$.

If $r_m(x)$ is not a monic polynomial, then we can readjust accordingly. Examples: $r_m(x) = \frac{11}{79}$, use $\gcd(f(x), g(x)) = 1$ and $r_m(x) = 2x + 2$, use $\gcd(f(x), g(x)) = x + 1$ since $2x + 2 = 2(x + 1)$.

What is $\gcd(x^4 + 1, x^3 + 1)$? Use the Euclidean Algorithm for Polynomials to determine your answer.


$1 - x$


$x^2 + 1$




$x + 1$

Select an assignment template