# How to find gcd of two polynomials if a different field?

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

• We can also apply the division algorithm over $\mathbb{F}_3$. The polynomials are coprime. – Dietrich Burde Apr 4 '16 at 17:34
• 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. – Arthur Apr 4 '16 at 17:45
• What is the defintion of $F_3$? is it the set $\{ 1,2,3 \}$ mod $3$? – ILoveMath Apr 4 '16 at 18:27

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