Sollya User's Manual

Name:

bezout Computes the gcd as well as the co-factors (Bezout coefficients)

Library name:

sollya_obj_t sollya_lib_bezout(sollya_obj_t, sollya_obj_t)

Usage:

bezout(p, q) : (function, function) -> structure

Parameters:

p is a constant or a polynomial.
q is a constant or a polynomial.

Description:

When both p and q are integers, bezout(p,q) computes the greatest common divisor g of these two integers, i.e., the greatest non-negative integer g dividing both p and q, as well as co-factors (Bezout coefficients), i.e., a and b such that a * p + b * q = g.
bezout always returns a structure containing four elements, g, r, a and b. These four elements always satisfy the following two properties: gcd(g,r) = gcd(p,q) and a * p + b * q = g. In addition, the tool tries to ensure r = 0. This latter property cannot always be ensured, in particular, it cannot be ensured for constant expression such that r becomes zero but the tool is unable to prove this fact. bezout ensures that g is the greatest common divisor of p and q only if r ends up being zero.
When both p and q are rational numbers, say s/t and u/v, bezout(p,q) computes the greatest common divisor of s * v and u * t, divided by the product of the denominators, t * v, as well as co-factors, still satisfying a * p + b * q = g.
When both p and q are constants but at least one of them is no rational number, bezout does not run the extended Euclidian algorithm to reduce gcd(p,q), i.e., the two elements g, r of the returned structure contain copies of the inputs p and q. The elements a and b are set to 0 and 1 accordingly. bezout differs from the gcd command in this point.
When both p and q are polynomials with at least one being non-constant, bezout(p,q) returns the polynomial of greatest degree dividing both p and q, and whose leading coefficient is the greatest common divisor of the leading coefficients of p and q. Polynomial co-factors (Bezout coefficients), i.e., a and b such that a * p + b * q = g, are returned as well.
Similarly to the cases documented for div and mod, bezout may fail to return the unique polynomial of largest degree dividing both p and q in cases when certain coefficients of either p or q are constant expressions for which the tool is unable to determine whether they are zero or not. These cases typically involve polynomials whose leading coefficient is zero but the tool is unable to detect this fact. In contrast to the gcd command, the bezout command is completely safe in this respect, as it returns not only an alleged greatest common divisor g but also the final remainder r obtained in the extended Euclidian algorithm. The two properties gcd(g,r) = gcd(p,q) and a * p + b * q = g are always satisfied for the four elements of the returned structure.
When at least one of p or q is a function that is no polynomial, bezout does not run the extended Euclidian algorithm to reduce gcd(p,q), i.e., the two elements g, r of the returned structure contain copies of the inputs p and q. The elements a and b are set to 0 and 1 accordingly. bezout differs from the gcd command in this point.

Example 1:

   > bezout(1001, 231);
   { .b = -4, .a = 1, .r = 0, .g = 77 }
   > bezout(13, 17);
   { .b = -3, .a = 4, .r = 0, .g = 1 }
   > bezout(-210, 462);
   { .b = 1, .a = 2, .r = 0, .g = 42 }

Example 2:

   > rationalmode = on!;
   > bezout(6/7, 33/13);
   { .b = -1, .a = 3, .r = 0, .g = 3 / 91 }

Example 3:

> bezout(exp(13),sin(17));
{ .b = 0, .a = 1, .r = -0.96139749187955685726163694486915609849206725405894, .g = 4.4241339200892050332610277594908828178439130606059e5 }

Example 4:

   > bezout(24 + 68 * x + 74 * x^2 + 39 * x^3 + 10 * x^4 + x^5, 480 + 776 * x + 476 * x^2 + 138 * x^3 + 19 * x^4 + x^5);
   { .b = 9.1666666666666666666666666666666666666666666666665e-2 + x * (0.125 + x * 5e-2), .a = -1.6666666666666666666666666666666666666666666666667 + x * (-0.575 + x * (-5e-2)), .r = 0, .g = 4 + x * (4 + x) }
   > bezout(1001 * x^2, 231 * x);
   { .b = 0.33333333333333333333333333333333333333333333333333, .a = 0, .r = 0, .g = x * 77 }

Example 5:

> bezout(exp(x), x^2);
{ .b = 0, .a = 1, .r = x^2, .g = exp(x) }