0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ so $1$ because the degree is 0? or because $1x^0$? $\endgroup$ – user32091 Nov 26 '17 at 22:01
  • 1
    $\begingroup$ @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. $\endgroup$ – John Doe Nov 26 '17 at 22:03
  • $\begingroup$ 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? $\endgroup$ – user32091 Nov 26 '17 at 22:10
  • $\begingroup$ 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. $\endgroup$ – John Doe Nov 26 '17 at 22:12
  • $\begingroup$ 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.$ $\endgroup$ – Will Jagy Nov 26 '17 at 23:49
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – John Doe Nov 26 '17 at 22:16
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user32091 Nov 27 '17 at 6:17
  • $\begingroup$ @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. $\endgroup$ – Will Jagy Nov 27 '17 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.