Computer Algebra

# Checking whether a multivariate polynomial is divisible by another

I have a small problem in implementing Division algorithm in k[x1, …, xn] with Maple, that is I don’t know exactly Maple does support to let me know whether a multivariate polynomial f is divisible by a multivariate polynomial g. So I decide to write my own procedure for this purpose (assume that I must not use NormalForm in package Groebner).

Input: LT(f), LT(g) (leading term of f, g)
Output:

• true if f is divisible by g
• false if f is not divisible by g

Example: Let us divide $\ f = 2.x^3.y.z$ by $\ g = 3.x^2.y$ (Exactly, these are the leading term of f, g)
Idea:

• Step 1: $\ LM (g) = x^2.y$ (leading monomial of g). So we set $\ varList = [x^2, y]$
• Step 2: from varList, find the remainder of f on division by each element in it. If there is a remainder <> 0, f is not divisible by g.

$\ f = 2.x^3.y.z = 2.x.y.z.(x^2) + 0$
$\ f = 2.x^3.y.z = 2.x^3.z.(y) + 0$
So f is divisible by g.

Here is the sample maple program. Assume that we only consider k[x,y,z]
> with(Groebner);

> isDivisible := proc (f, g)
>     local lMOfg, varList, n, i, mElement, vElement, r;
>
>     # Why do I use w here ?! Notice I already assume that we consider k[x,y,z]
>     lMOfg := LeadingMonomial (g * w, plex(z, y, x, w));
>     varList := op (lMOfg);
>     n := nops (lMOfg);
>
>     for i from 1 to (n – 1) do
>         mElement := op (i, lMOfg);
>         vElement := (indets(mElement))[1];
>         r := rem (f, mElement, vElement);
>         if (r <> 0) then
>             return false;
>         end if;
>     end do;
>     return true;
>
> end proc;

$\ \copyright proSeverus$