finding the greatest common divisor of two polynomial, I'm stuck

Question

I'm trying to find the greates common divisor of two polynomials. The polynomials are: \begin{align*} p_1 &= x^3+3x+1\\ p_2 &= x^4+1 \end{align*} Matlab is telling me that the GCD is 1, and that's also what I was expected.

However when I try to do It by hand it dosn't equal to 1, so what am I doing wrong?(I'm using Long division and writing it as Euclidian algorithm).

\begin{align*} x^4+1 &= (x^3+3x+1) \cdot x -(3x^2-x+1)\\ x^3+3x+1 &= (-3x^2-x+1) \cdot (\frac{-x}{3}+\frac{1}{9}) + (\frac{31x}{9}+\frac{8}{9})\\ -3x^2-x+1 &= (\frac{31x}{9}+\frac{8}{9})\cdot (\frac{-27x}{31} - \frac{63}{961})+ \frac{1017}{961}\\ \frac{31x}{9}+\frac{8}{9}&=\frac{1017}{961}\cdot (\frac{29791x}{9153}+\frac{7688}{9153})+\frac{8}{9}\\ \frac{1017}{961} &= \frac{8}{9} \cdot \frac{9153}{7688} + 0 \end{align*}

so the GCD should be $= \frac{8}{9}$??

Answer 1

$8/9$ and $1$ are the "same thing" because there exists a unit in the ring $\mathbb R [x]$ that send one to the other (notice that $\frac{9}{8}$ is a unit).

You may be confused because the units in the ring of integers are only $1$ and $-1$.

The convention is to let $\gcd(P,Q)$ be monic when working with polynomials.

Answer 2

By greatest common divisor, when talking about polynomials, this means, find the greatest $n$ for which $x^n+a_{n-1} x^{n-1}+...+a_1 x+a_0$ divides both of your polynomials. Then the greatest common divisor is $$x^n+a_{n-1} x^{n-1}+...+a_1 x+a_0$$ In your example, $n=0$, so the greatest common divisor is $1$.
$\frac89$ is the same thing as it is just a scalar multiple of this, i.e. it is a polynomial of the same degree ($0$). We choose by convention that we want the coefficient of $x^n$ to be $1$, which is why MATLAB tells you it is $1$.

Answer 3

What I like to do for the Extended Euclidean Algorithm is not back substitution, which i can never remember, rather a (simple) continued fraction. There is not usually enough room with polynomials to write the continued fraction part sideways, so I write that sequence of fractions
vertically. The "extended" part then comes from the little 2 by 2 cross products always being $\pm 1.$ I cancel out some of the common factors, and in the end get $$ \left( x^{4} + 1 \right) \left( \frac{ 31 x^{2} - 8 x + 106 }{ 113 } \right) - \left( x^{3} + 3 x + 1 \right) \left( \frac{ 31 x^{3} - 8 x^{2} + 13 x - 7 }{ 113 } \right) = \left( 1 \right) $$ which is a confirmation that the original polynomials are coprime.

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

    parisize = 4000000, primelimit = 500509
    ? (x^4 + 1) * (31 * x^2 - 8 * x + 106) - (x^3 + 3 * x + 1) * (31 * x^3 - 8 * x^2 + 13 * x - 7) 
    %1 = 113
    ? hooray!
      ***   at top-level: hooray!
      ***                 ^-------
      ***   gtos expected an integer, got 'hooray'.
      ***   Break loop: type 'break' to go back to GP
    break> break

$$ \left( x^{4} + 1 \right) $$

$$ \left( x^{3} + 3 x + 1 \right) $$

$$ \left( x^{4} + 1 \right) = \left( x^{3} + 3 x + 1 \right) \cdot \color{magenta}{ \left( x \right) } + \left( - 3 x^{2} - x + 1 \right) $$ $$ \left( x^{3} + 3 x + 1 \right) = \left( - 3 x^{2} - x + 1 \right) \cdot \color{magenta}{ \left( \frac{ - 3 x + 1 }{ 9 } \right) } + \left( \frac{ 31 x + 8 }{ 9 } \right) $$ $$ \left( - 3 x^{2} - x + 1 \right) = \left( \frac{ 31 x + 8 }{ 9 } \right) \cdot \color{magenta}{ \left( \frac{ - 837 x - 63 }{ 961 } \right) } + \left( \frac{ 1017}{961 } \right) $$ $$ \left( \frac{ 31 x + 8 }{ 9 } \right) = \left( \frac{ 1017}{961 } \right) \cdot \color{magenta}{ \left( \frac{ 29791 x + 7688 }{ 9153 } \right) } + \left( 0 \right) $$ $$ \frac{ 0}{1} $$ $$ \frac{ 1}{0} $$ $$ \color{magenta}{ \left( x \right) } \Longrightarrow \Longrightarrow \frac{ \left( x \right) }{ \left( 1 \right) } $$ $$ \color{magenta}{ \left( \frac{ - 3 x + 1 }{ 9 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ - 3 x^{2} + x + 9 }{ 9 } \right) }{ \left( \frac{ - 3 x + 1 }{ 9 } \right) } $$ $$ \color{magenta}{ \left( \frac{ - 837 x - 63 }{ 961 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 279 x^{3} - 72 x^{2} + 117 x - 63 }{ 961 } \right) }{ \left( \frac{ 279 x^{2} - 72 x + 954 }{ 961 } \right) } $$ $$ \color{magenta}{ \left( \frac{ 29791 x + 7688 }{ 9153 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 961 x^{4} + 961 }{ 1017 } \right) }{ \left( \frac{ 961 x^{3} + 2883 x + 961 }{ 1017 } \right) } $$ $$ \left( x^{4} + 1 \right) \left( \frac{ 31 x^{2} - 8 x + 106 }{ 113 } \right) - \left( x^{3} + 3 x + 1 \right) \left( \frac{ 31 x^{3} - 8 x^{2} + 13 x - 7 }{ 113 } \right) = \left( 1 \right) $$

Answer 4

This one is just an illustration of using simple continued fractions to solve $ax+by = 1.$ One convergent (good approximation) for $\pi$ is $\frac{355}{113}.$ Let us show the gcd is one and solve the Bezout thing

$$ \gcd( 355, 113 ) = ??? $$

$$ \frac{ 355 }{ 113 } = 3 + \frac{ 16 }{ 113 } $$ $$ \frac{ 113 }{ 16 } = 7 + \frac{ 1 }{ 16 } $$ $$ \frac{ 16 }{ 1 } = 16 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccc} & & 3 & & 7 & & 16 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 3 }{ 1 } & & \frac{ 22 }{ 7 } & & \frac{ 355 }{ 113 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 3 \\ \frac{ 3 }{ 1 } & \mbox{digit} & 7 \\ \frac{ 22 }{ 7 } & \mbox{digit} & 16 \\ \frac{ 355 }{ 113 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 355 \cdot 7 - 113 \cdot 22 = -1 $$ Note how this is just a little 2 by 2 crossed product from the displayed convergents in the continued fraction.

===============================================================================

This time I made one with a little longer continued fraction.

$$ \gcd( 1393, 972 ) = ??? $$

$$ \frac{ 1393 }{ 972 } = 1 + \frac{ 421 }{ 972 } $$ $$ \frac{ 972 }{ 421 } = 2 + \frac{ 130 }{ 421 } $$ $$ \frac{ 421 }{ 130 } = 3 + \frac{ 31 }{ 130 } $$ $$ \frac{ 130 }{ 31 } = 4 + \frac{ 6 }{ 31 } $$ $$ \frac{ 31 }{ 6 } = 5 + \frac{ 1 }{ 6 } $$ $$ \frac{ 6 }{ 1 } = 6 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccc} & & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 10 }{ 7 } & & \frac{ 43 }{ 30 } & & \frac{ 225 }{ 157 } & & \frac{ 1393 }{ 972 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 1 \\ \frac{ 1 }{ 1 } & \mbox{digit} & 2 \\ \frac{ 3 }{ 2 } & \mbox{digit} & 3 \\ \frac{ 10 }{ 7 } & \mbox{digit} & 4 \\ \frac{ 43 }{ 30 } & \mbox{digit} & 5 \\ \frac{ 225 }{ 157 } & \mbox{digit} & 6 \\ \frac{ 1393 }{ 972 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 1393 \cdot 157 - 972 \cdot 225 = 1 $$ Check how the cross products are all $\pm 1.$ For example $3 \cdot 7 - 2 \cdot 10 = 21 -20 = 1,$ then $10 \cdot 30 - 7 \cdot 43 = 300 - 301 = -1.$