1

Let $f(x) = x^3 - 6x^2 + x + 4$ and $g(x) = x^5 - 6x +1$. Using Euclidean algorithm I find $\gcd[f(x), g(x)] = 1$. How could I JUSTIFY that $h(x) = 1$ is the ACTUAL $\gcd$ of $f(x)$ and $g(x)$?

Thanks.

Natalie
  • 31
  • 5
    Does the Euclidean algorithm not count as a justification? If not, why not, and what does? If you're asking us what counts as a justification, why do you think EA doesn't count? – anon Oct 11 '13 at 00:21

1 Answers1

1

Actually Euclidean Algorithm is a really good proof.

One other way is to factorize one of the polynomials into linear polynomials. To do the find the zeroes of that polynomials. I'll use the polynomial $f(x)$ so the zeroes are at $x = 1$, $x=\frac 12 (5 \pm \sqrt{41})$.

So we can factorize it as:

$$x^3 - 6x^2 + x + 4 = (x-1)(\frac 12 (x-5+\sqrt{41}))(\frac 12 (x-5-\sqrt{41}))$$ $$x^3 - 6x^2 + x + 4 = \frac14(x-1)(x-5+\sqrt{41})(x-5-\sqrt{41})$$

So now we need to check which of this factors divide $g(x)$. Using the Polynomial remainder Theorem we know that a linear polynomial of the type $(x-a)$ divides some polynomial $p(x)$ if and only if $p(a) = 0$

So we have three cases to check those are $a = 1$, $a = 5 + \sqrt{41}$ and $a = 5 - \sqrt{41}$. And for all three cases we'll get that $g(a) \neq 0$, so neither of the factors of $f(x)$ is divisor of $g(x)$, i.e $gcd(f(x),g(x)) = 1$

Also sometimes to get rid of those ugly calculation you can use Sylvester matrix to check whether 2 polynomials are coprime. You can read how to generate one reading the intructions in the link so for this example the matrix would look like:

$$\begin{bmatrix} 1 & 0 & 0 & 0 & -6 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & -6 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & -6 & 1 \\ 1 & -6 & 1 & 4 & 0 & 0 & 0 & 0 \\ 0 & 1 & -6 & 1 & 4 & 0 & 0 & 0 \\ 0 & 0 & 1 & -6 & 1 & 4 & 0 & 0 \\ 0 & 0 & 0 & 1 & -6 & 1 & 4 & 0 \\ 0 & 0 & 0 & 0 & 1 & -6 & 1 & 4 \end{bmatrix}$$

Take the determinant of it. If it's $0$ the two polynomials have a common root and a common factor. Otherwise they are coprime and you can stop your caclulation there. So for this two polynomials we have:

$$\begin{vmatrix} 1 & 0 & 0 & 0 & -6 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & -6 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & -6 & 1 \\ 1 & -6 & 1 & 4 & 0 & 0 & 0 & 0 \\ 0 & 1 & -6 & 1 & 4 & 0 & 0 & 0 \\ 0 & 0 & 1 & -6 & 1 & 4 & 0 & 0 \\ 0 & 0 & 0 & 1 & -6 & 1 & 4 & 0 \\ 0 & 0 & 0 & 0 & 1 & -6 & 1 & 4 \end{vmatrix} = 120784$$

So clearly this isn't equal to $0$ and we can conclude that these two polynomails are coprime.

Stefan4024
  • 35,843