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