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

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}$??

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

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

• so $1$ because the degree is 0? or because $1x^0$? – user32091 Nov 26 '17 at 22:01
• @user32091 Yes since, $1=1\cdot x^0$ is a polynomial of degree $0$. You can say it in either way, since they are the same. – John Doe Nov 26 '17 at 22:03
• so it could be any number $n$ because $n \cdot x^0$ but we just by convention choose 1 ? Thanks 😊! @JohnDoe One more question, i need to solve Bézout identity so $p_1U+$p_2V = 1$how to I do that ? Do i scale everything so 8/9 =1 or do I just use 8/9 insted of 1? – user32091 Nov 26 '17 at 22:10 • Yep it could be any$n$. Since the convention is to use$1$(and it will likely make calculations much easier), I would still use$1$. I think Will Jagy's answer goes through this calculation. – John Doe Nov 26 '17 at 22:12 • John, I did the Extended Euclidean algorithm. I like to write the "back-substitution" part as, instead, a simple continued fraction. Just as with ordinary integers, we get the 2 by 2 cross products coming out$\pm 1.$– Will Jagy Nov 26 '17 at 23:49 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)$$ • Could you add a few sentences and words to this to add some structure? It is (probably - assuming calculations are correct) fine mathematically but I'm sure that would improve the answer considerable. – John Doe Nov 26 '17 at 22:16 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.$• I don’t understand all of it, How do u get The Numbers$\frac{0}{1}, \frac{1}{0},...,\frac{225}{157}. And how do u know how many digit they have? – user32091 Nov 27 '17 at 6:17
• @user32091 well, if you don't know continued fractions, this will not be attractive. Why don't you find $\gcd(1393, 972)$ and $1393x+972y = 1$ your way, see how the methods compare. – Will Jagy Nov 27 '17 at 18:06