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

[toni07]

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.

 

[Fernando Revilla]

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.

Use the Euclidean algorithm. Perhaps this thread helps:

http://mathhelpboards.com/linear-abstract-algebra-14/field-extensions-basic-theory-6565.html#post29923

 

[toni07]

Use the Euclidean algorithm. Perhaps this thread helps:

http://mathhelpboards.com/linear-abstract-algebra-14/field-extensions-basic-theory-6565.html#post29923

I already used the Euclidean algorithm to get the gcd which is 2, but I need help with the rest of the question.

 

[I like Serena]

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$

 

[Deveno]

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.

 

[toni07]

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.

 

[I like Serena]

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]

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$.