Algorithm to find the GCD of $f,g\in F[x,y]$

Input: $f,g\in F[x,y]$.

Output: $gcd(f,g)$.

• Compute the Gröbner basis $G$ of the ideal $I=\langle tf , (1-t)g\rangle$ with respect to the ordering $t< x< y$.

• Take $p$ in $G$ such that $p$ involves only $x$ and $y$. If there is no such $p$ in $G$ then
  $$GCD(f, g) = 1.$$
  Otherwise
  $$GCD(f, g) = fg/p.$$

Example 2.8.15   Let $f(x,y)=x^2-y^2$ and $g(x,y)=x^3-y^3$. The Gröbner basis of $I=(tf(x,y),(1-t)g(x,y))$ using the lexicographic ordering defined by $t< x< y$ is:

$$G=\{-y x^3+y^4-x^4+xy^3,ytx^2+x^3-y^3-tx^3,-tx^2+ty^2\}.$$

Taking $p=-y x^3+y^4-x^4+xy^3$, we have $gcd(f,g)=f(x,y)g(x,y)/p= y-x$.

Exercise 2.8.16   Consider a curve parameterized by $x=t$, $y=2t^2$, $z=t^5$. Using a Gröbner basis, find the algebraic equations for the curve.

(Ans: $[y=2x^2$, $z=x^5$.)

Exercise 2.8.17   Let $f(x,y)=x^2-4y^2$ and $g(x,y)=x^2-4xy+4y^2$. Using a Gröbner basis, find the gcd of $f$ and $g$.

(Ans: $x-2y$.)

Exercise 2.8.18   Let $f,g$ be monomials as above. Based on the analog with definitions on $\mathbb{N}$, define the greatest common divisor, $gcd(f,g)$ and the least common multiple, $lcm(f,g)$, of $f,g$.

Exercise 2.8.19   Let $f(x_1,x_2)=x_1^4x_2^3$ and $g(x_1,x_2)=x_1^2x_2^6$. Find $gcd(f,g)$ and $lcm(f,g)$.

Exercise 2.8.20   Let $f(x_1,x_2,x_3)=x_1+x_2+x_3 +x_2x_3$, $g(x_1,x_2,x_3)=x_1+x_2$. Find $S(f,g)$, where

(a) $<$ is the lexicographical ordering,

(b) $<$ is the graded lexicographic ordering.

Exercise 2.8.21   Let $f(x_1,x_2,x_3)=x_1-13x_2^2-12x_3^2$, $g(x_1,x_2,x_3)=x_1^2-x_1x_2+92x_3$. Find $S(f,g)$, where

(a) $<$ is the lexicographical ordering,

(b) $<$ is the graded lexicographic ordering.

Exercise 2.8.22   Let $<$ be the graded lexicographic ordering. Let $f_1(x,y)=xy-2x$, $f_2(x,y)=x^2-y$, $f_3(x)=y^2-2y$. Show $S(f_1,f_2)=y^2-2x^2$, $S(f_1,f_3)=0$.

Exercise 2.8.23   Find $F$ be the smallest field that contains $\mathbb{Q}$, $\sqrt{3}$, and $i6^{1/3}$. Prove that $F$ can be generated by just the single element ( $\alpha =\sqrt{3} +i6^{1/3}$ (so that the smallest field containing $\mathbb{Q}$ and $\alpha$ is exactly $F$), by expressing both $\sqrt{3}$ and $i6^{1/3}$ as polynomials in $\alpha$. (Hint: What does the Groebner basis of $(x^2-3, y^2+1, z^3-6, w - x - y z )$ have to do with this problem?)

Exercise 2.8.24   Let $<$ be the graded lexicographic ordering. Let $f_1(x,y)=xy-2x$, $f_2(x,y)=x^2-y$, $G=\{f_1,f_2\}$. Show $y^2-2x^2 \stackrel{G}{\rightarrow}y^2-2y$.

Exercise 2.8.25   Let $<$ be graded lexicographical ordering - terms are listed from highest to lowest degree and $x>y>z$. Let $f(x,y,z)=2x^2z^4+xz^3+y^3z^3$. Order the terms of $f$ from highest to lowest.

Exercise 2.8.26   Let $f(x_1,x_2,x_3)=x_1+x_2+x_3 +x_2x_3$. Find $lt_<(f)$, where

(a) $<$ is the lexicographical ordering,

(b) $<$ is the graded lexicographic ordering.

Exercise 2.8.27   Find the polynomial of smallest degree with integer coefficients that has $4-\frac{2-5^{1/3}}{3-2i}$ as a root. (Hint: What does the Grobner basis of $(x^3-5, y^2+1, z(3-2y)-(2-x))$ have to do with this problem?)