# Gröbner Basis and Division Algorithm

I recently read a lemma on a course in Commutative Algebra that states,

If $G$ is a Gröbner Basis for an Ideal $I$ in $k[x_{1},...,x_{n}]$, then a polynomial $f$ belongs to $I$ if and only if $f$ on division by $G$ (we can do this using the division algorithm for polynomials) has a remainder $0$.

My question is why would we need to go through all the trouble of calculating Gröbner basis, when we can instead say that every ideal in $k[x_{1},x_{2}...x_{n}]$ is finitely generated by $f_{1},f_{2},f_{3},...f_{s}$ (By Hilbert's Basis Theorem) and therefore divide $f$ by these $f_{i}$'s and check whether the remainder is $0$?

The reason is first that the remainder of division is not unique if we don't have a Gröbner basis, and second, the remainder can be nonzero, even if $f$ lies in $I$.

Example:

Take $I=(y^2-x,yx-y)$ (in that order) and use deglex with $y>x$ in $\mathbf Q[x,y]$ Then $f=y^2x-x= (y^2-x) +y(yx-y)\in I$, but you can check the remainder of the division is $x^2-x$.

• Oh ok, didn't realise that actually, so what exactly is it about the Grobner Basis that makes it such an ideal basis to work with? Also another question about the monomial orders, I am quite confused when we reverse the ordering like the one you suggested in your example. What exaclty do we do when we say $y>x$ using the deglex – user1314 Apr 12 '15 at 13:22
• Well, with a Grobner basis, you can test if a polynomial belongs to an ideal: the remainder upon division by the Grobner basis must be $0$. ou can test the equality of ideals, test if an algebraic subset of $K^n$ is empty or finite. As for deglex,monomilal ordering is based on: $1.$ the total degree; $2.$ for for monomials of the same total degree, you use lexicographical order. So $y>x$ or $x>y$ leads to different results. – Bernard Apr 12 '15 at 14:08

Hilbert's basis theorem is an existence theorem. It is not constructive. We know there are basis but how to find them is a different story. Groebner basis is not about existence, it is about finding an algorithm which is efficient. Grobner basis is a generalization of Gaussian elimination where now we consider non-linear (polynomial) equations. The uniqueness of the remainder comes together with other (at list 5 more) properties (equivalences) which make the theory very solid.

## protected by user26857Aug 15 '15 at 6:45

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?