0
$\begingroup$

I am trying to understand how to find the greatest common divisor of two polynomials in fields different that $\mathbb{R}$ or $\mathbb{Q}$. For example, how would be the procedure to calculate gcd of $x^3+2x+1$ and $x^3+2x^2+2$ in $\mathbb{F}_3[x]$?

$\endgroup$
  • 3
    $\begingroup$ We can also apply the division algorithm over $\mathbb{F}_3$. The polynomials are coprime. $\endgroup$ – Dietrich Burde Apr 4 '16 at 17:34
  • 2
    $\begingroup$ Euclid's algorithm works in $k[x]$ for any field $k$. Note that "coprime" in that case means not that you end up with $1$ when applying the algorithm, but that you end up with any non-zero constant term. $\endgroup$ – Arthur Apr 4 '16 at 17:45
  • $\begingroup$ What is the defintion of $F_3$? is it the set $\{ 1,2,3 \}$ mod $3$? $\endgroup$ – ILoveMath Apr 4 '16 at 18:27
1
$\begingroup$

Getting better with this. In the field with three elements, we can change $2$ to $-1$ as needed.

Begin $$ \frac{x^3 - x^2 - 1}{x^3 - x + 1}, $$ quotient = $1,$ remainder = $-x^2 + x + 1.$

$$ \frac{x^3 - x + 1}{-x^2 + x + 1}, $$ quotient = $-x-1,$ remainder = $-2x+2 = x-1.$

$$ \frac{-x^2 + x + 1}{x-1}, $$ quotient = $-x,$ remainder = $1.$

$$ \frac{x-1}{1}, $$ quotient = $x-1,$ remainder = $0.$

In the sense of continued fractions, which i prefer for bookkeeping, partial quotients $$ 1, \; \; -x-1, \; \; -x, \; \;x-1 $$ Convergents $$ \frac{0}{1}, \; \; \frac{1}{0}, \; \; \frac{1}{1}, \; \; \frac{-x}{-x-1}, \; \; \frac{x^2 + 1}{x^2 + x + 1}, \; \; \frac{x^3 - x^2 - 1}{x^3 - x + 1}. $$

Finally $$ (x^2 + 1)(x^3 - x + 1) = x^5 + x^2 - x + 1, $$ $$ (x^2 + x + 1)(x^3 - x^2 - 1) = x^5 + x^2 - x - 1 $$

$$ (x^2 + 1)(x^3 - x + 1) - (x^2 + x + 1)(x^3 - x^2 - 1) = 2 = - 1. $$

$\endgroup$

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.