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)

  • 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)

  • 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


Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s