# Let f(x) = x^2 + 1 and g(x) = x^3 + 1.

#### crypt50

##### New member
a) Over the field Q, compute h(x) = gcd(f(x), g(x)), and fi nd polynomials a(x) and b(x) such that h(x) = a(x)f(x) + b(x)g(x).
(b) Same question over the fi eld F_2 = {0, 1}.

I already computed the gcd(f(x), g(x)) to be 2, but I don't really understand how I'm supposed to find a(x) and b(x), and the difference the result is supposed to have when compared with result of part b.

MHB Math Helper

#### Klaas van Aarsen

##### MHB Seeker
Staff member
I already used the Euclidean algorithm to get the gcd which is 2, but I need help with the rest of the question.
The extended Euclidean algorithm (for $\mathbb Q[x]$) also provides the factors:

\begin{array}{rcrcrl}
1 \cdot (x^3 + 1) &+& 0 \cdot (x^2 + 1) &=& x^3 + 1 \\
0 \cdot (x^3 + 1) &+& 1 \cdot (x^2 + 1) &=& x^2 + 1 & \text{times (-x) and add to previous} \\
\hline \\
1 \cdot (x^3 + 1) &+& (-x) \cdot (x^2 + 1) &=& -x + 1 & \text{times (x) and add to previous} \\
x \cdot (x^3 + 1) &+& (-x^2 + 1) \cdot (x^2 + 1) &=& x + 1 & \text{times (1) and add to previous} \\
(x+1)\cdot (x^3 + 1) &+& (-x^2 - x + 1) \cdot (x^2 + 1) &=& 2 & \text{divide by 2} \\
\frac 12(x+1)\cdot (x^3 + 1) &+&\frac 12 (-x^2 - x + 1) \cdot (x^2 + 1) &=& 1
\end{array}
$\blacksquare$

Last edited:

#### Deveno

##### Well-known member
MHB Math Scholar
I think it's misleading to say "the gcd is 2", since any gcd is only determined up to a unit factor. In $\Bbb Q$, 2 is a unit, so we can claim just as easily that the gcd is 1, or 5. The important thing is that the gcd is of degree 0, so in particular is non-zero.

Over the field $F_2$, things are quite a bit different. For example, in $F_2$, we have that $x^2 + 1$ splits completely as:

$x^2 + 1 = (x + 1)(x + 1)$.

It should also be clear that in $F_2$ we have:

$x^3 + 1 = (x + 1)(x^2 + x + 1)$ where both of these factors are irreducible.

To show that $x + 1$ is the gcd (I use "the" here, because $F_2$ only HAS one unit, 1), it suffices to show $x^2 + 1$ does not divide $x^3 + 1$. I leave it to you to devise $a(x),b(x)$ a little algebraic tinkering should show you the proper polynomials to pick.

Last edited:

#### crypt50

##### New member
I think it's misleading to say "the gcd is 2", since any gcd is only determined up to a unit factor. In $\Bbb Q$, 2 is a unit, so we can claim just as easily that the gcd is 1, or 5. The important thing is that the gcd is of degree 0, so in particular is non-zero.

Over the field $F_2$, things are quite a bit different. For example, in $F_2$, we have that $x^2 + 1$ splits completely as:

$x^2 + 1 = (x + 1)(x + 1)$.

It should also be clear that in $F_2$ we have:

$x^3 + 1 = (x + 1)(x^2 + x + 1)$ where both of these factors are irreducible.

To show that $x + 1$ is the gcd (I use "the" here, because $F_2$ only HAS one unit, 1), it suffices to show $x^2 + 1$ does not divide $x^3 + 1$. I leave it to you to devise $a(x),b(x)$ a little algebraic tinkering should show you the proper polynomials to pick.
My main problem is finding a(x), and b(x), and I still don't know how.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
My main problem is finding a(x), and b(x), and I still don't know how.
You can read it off from the extended euclidean algorithm I showed.
Take each coefficient mod 2.
Then the algorithm stops a couple of lines earlier, where the value 2 was found, which is actually 0 (mod 2).
The line before that line shows the gcd, a(x), and b(x).

#### Deveno

##### Well-known member
MHB Math Scholar
Yes, that works, and is the "rote" way to find it (no real thinking is required).

For example, we first divide $x^3 + 1$ by $x^2 + 1$ obtaining:

$x^3 + 1 = x(x^2 + 1) + x + 1$ (step one)

$x^2 + 1 = (x + 1)(x + 1) + 0$ (step two)

as this has a remainder of 0, we "back up one step" and find the gcd is $x + 1$:

$x + 1 = x^3 + 1 - x(x^2 + 1) = x^3 + 1 + x(x^2 + 1)$

(because in $F_2, 1 = -1$), which tells us that $a(x) = x, b(x) = 1$.

As I remarked earlier, though, just by "playing around" one quickly discovers that:

$x(x^2 + 1) + (1)(x^3 + 1) = x^3 + x + x^3 + 1 = 2x^3 + x + 1 = x + 1$.

Last edited: