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's_algorithm