Multivariate division algorithm

Remarks

The algorithm stops, because each step makes the leading monomial of $p$ strictly smaller, or makes $p$ zero, and a monomial order is a well-order. The output satisfies $f = q_1 g_1 + \cdots + q_s g_s + r$. No monomial of $r$ is divisible by any $\operatorname{LT}(g_i)$, and the leading monomial of $q_i g_i$ is at most that of $f$ whenever $q_i g_i \ne 0$.

Example: in $k[x, y]$ with the lexicographic order $x > y$, divide $f = x^2 y + x y^2 + y^2$ by $(g_1, g_2) = (xy - 1, \; y^2 - 1)$. The steps give $q_1 = x + y$, $q_2 = 1$ and $r = x + y + 1$; check: $(x + y)(xy - 1) + (y^2 - 1) + x + y + 1 = x^2 y + x y^2 + y^2$. With the list in the order $(y^2 - 1, \; xy - 1)$, the algorithm gives the quotients $x + 1$ for $y^2 - 1$ and $x$ for $xy - 1$, and the remainder $2x + 1$. So in general the remainder depends on the order of the list. For a Gröbner basis, the remainder does not depend on the order, and it is zero exactly when $f$ lies in the ideal $(g_1, \ldots, g_s)$.