It is said in many places (for example, on the Wikipedia article for Buchberger's algorithm) that Buchberger's algorithm to find Groebner basis is a generalization of Euclid's GCD algorithm.
This is not obvious to me. Just think about two polynomials $f(x)=a_n x^n + \cdots a_0$, and $g(x)=b_m x^m + \cdots b_0$, with $n>m$. Start by finding the subtraction polynomial $S(f,g)$, here I do not see a clue of Euclid's algoritm and what does it have to do with Euclid's GCD algorithm.
Please do not respond that both Euclid and Buchberger produce the same result. I already know that. I am questioning about how one algorithm (Buchberger's) reduce to the other (Euclid's) for univariate polynomials.
Any clue?
Thanks.
Thanks to @user26857, for his great hint.
Assume \begin{equation} f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 , \quad g(x) = b_m x^m + b_{n-1} x^{n-1} + \cdots + b_0 , \end{equation} and $n \ge m$, $a_n \ne 0 \ne b_m$. We have $\text{LM}(f)=x^n$ and $\text{LM}(g)=x^m$. We call $L= \text{LCM}[ \, \text{LM}(f), \text{LM}(g)] = x^{n}$. Then by definition \begin{eqnarray} S(f,g) &=& \frac{L}{\text{LT}(f)} f - \frac{L}{\text{LT}(g)} g \\ &=& \frac{x^n}{a_n x^n} f - \frac{x^n}{b_m x^m} g \\ &=& \frac{1}{a_n} \left ( f - \frac{ a_n x_n}{b_m x^m}g \right) \\ &=& \frac{1}{a_n} \left (f - \frac{\text{LT}(f)}{\text{LT}(g)} g \right ) \end{eqnarray} On the other hand the first step on the Euclidean algorithm is the division of $f$ by $g$. This step is achieved by finding the remainder \begin{equation} r_1 = f - \frac{\text{LT}(f)}{{\text{LT}(g)}} g . \end{equation} Setting the $1/a_n$ aside (up to a multiplication by scalar any non-zero multiple of the GCD$(f,g)$ is also Gr\"{o}bner basis member) we have that $S(f,g)=r_1$. If $\text{deg}(r_1) < \text{deg}(f)$ we are done with this remainder, otherwise we keep reducing it until $\text{deg}(r_1) < \text{deg}(f)$.
The Buchberger algorithm starts with $G=\{f, g \}$, and then, if $r_1 \ne 0$, add (append) $r$ to $G$. That is $G = \{f, g , r_1 \}$. The next step is to reduce $r_1$ with respect to $G$. Since $\text{deg}(r_1) < \text{deg}(f)$, we only need to reduce $r$ with respect to $g$. That is, we divide $r$ by $g$, and keep doing this until $r_n=0$. (We do not prove here that the algorithm finishes. It does. That is not the purpose of this exercise). Then $G=\{f, r_1, \dots, r_{n-1} \}$. We find that $\text{GCD}(f,g)=r_{n-1}$, and it is found as if we were doing Euclid's algorithm instead of Buchberger's algorithm.
That $G$ can be reduced to $G=\{r_{n-1} \}= \{ \text{GCD}(f,g)\}$ is another story.