Input: divisor set \(\{ f_1, \cdots , f_s\} \) and dividend \(f\)

Output: quotients \(q_1, \cdots , q_s\) and remainder \(r\)

• \(\forall \, i,\, q_i := 0;\, r := 0\)

• \(p := f\)

• while \(p \ne 0\):

  • \(i := 1\)

  • \(DivisionOccured := False\)

  • while \(i \le s\) and not \(DivisionOccured\):

    • if \(\mathrm{LT}(f_i) \mid \mathrm{LT}(p)\):

      • \(q_i := q_i + \mathrm{LT}(p) / \mathrm{LT}(f_i)\)

      • \(p := p - (\mathrm{LT}(p) / \mathrm{LT}(f_i))f_i\)

    • else:

      • \(i := i + 1\)

  • if not \(DivisionOccured\):

    • \(r := r + \mathrm{LT}(p)\)

    • \(p := p - \mathrm{LT}(p)\)

  return \(q_1, \cdots , q_s, r\)

Define the least common multiple \(\gamma = \mathrm{lcm}(\alpha , \beta )\) of two monomials \(\alpha , \beta \) as \(\gamma _i = \max (\alpha _i, \beta _i)\). The S-polynomial of two polynomials \(f\) and \(g\), given a monomial order, is

We say each part of above, i.e.

the S-pair of \(f\) and \(g\).

For \(G = \{ g_1, \cdots , g_t\} \subseteq k[x_1, \cdots , x_n]\) and \(f \in k[x_1, \cdots , x_n]\), a standard representation of \(f\) by \(G\) is, if exists, an equality

where \(A_k g_k = 0\) or \(\mathrm{LM}(f) \ge \mathrm{LM}(A_k g_k)\) for every \(1 \le k \le t\). If such a standard representation exists, we say \(f\) reduces to zero modulo \(G\) and notate it as