Number Theory

Free Version

Upgrade subject to access all content


Euclidean Algorithm in $\left(\mathbb{Z} / 2\mathbb{Z}\right)[x]$


Let $\mathbb{Z} / 2\mathbb{Z} = \{ \overline{a} | a = 0, 1\}$ and $\overline{a} = \{a + 2b | b \in \mathbb{Z}\}$. 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, exs: $\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)$.

Recall that $\mathbb{Z} / 2\mathbb{Z}$ is a field and so we can use the Euclidean Algorithm for Polynomials when trying to determine the greatest common divisor of two polynomials in $\left(\mathbb{Z} / 2\mathbb{Z}\right)[x]$.

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




$x + \overline{1}$




$x^2 + \overline{1}$