A Groebner Basis is a mathematical tool for manipulating expressions. See http://en.wikipedia.org/wiki/Groebner_Basis which is not an easy read. There is an implementation available with SymbolicCpp. -- JohnFletcher

It is used to decide divisability of polynoms because repeated reduction (division) is guaranteed to terminate (simplified). The key algorithm is Buchbergers:

http://en.wikipedia.org/wiki/Buchberger%27s_algorithm

----
CategoryMath