 Algebraic - Maple Programming Help

Home : Support : Online Help : Mathematics : Algebra : Algebraic Numbers : Algebraic/GreatestCommonDivisor

Algebraic

 GreatestCommonDivisor
 gcd of polynomials with algebraic number coefficients

 Calling Sequence GreatestCommonDivisor(a, b, options) GreatestCommonDivisor(a, b, 'ca', 'cb', options) Gcd(a, b, options) Gcd(a, b, 'ca', 'cb', options)

Parameters

 a,b - polynomials with algebraic number coefficients ca,cb - names; will be assigned the cofactors options - (optional) equation(s) of the form keyword = value, where keyword is either 'symbolic', 'makeindependent', or 'characteristic'

Options

 • If the option 'symbolic'=true is given and a RootOf whose minimal polynomial factors nontrivially is detected, GreatestCommonDivisor will reduce it to a RootOf of lower degree by picking one of the factors arbitrarily. This will eliminate the possibility of a "reducible RootOf detected" error. The default is 'symbolic'=false.
 • If the option characteristic=p is given, where p is a nonnegative integer, the gcd is computed over an extension of the ring${\mathrm{ℤ}}_{p}$ of integers modulo p. The default is characteristic=0 and means that the gcd is computed over an extension of the rational numbers.
 • Note that if p is positive but not a prime, then ${\mathrm{ℤ}}_{p}$ is not a field, and the greatest common divisor may not exist or may not be unique.  GreatestCommonDivisor will attempt to compute a gcd anyway. If it does not succeed because it encounters an integer that has no inverse modulo p, it issues the error "zero divisor modulo p detected".
 • If the option 'makeindependent'=true is given, then GreatestCommonDivisor will always try to find a field representation for algebraic numbers in the input, regardless of how many algebraic objects the input contains. If the input contains many RootOfs, then this can be a very expensive calculation. If 'makeindependent'=false is given, then no independence checking is performed. The default is 'makeindependent'=FAIL, in which case algebraic dependencies will only be checked for if there are $4$ or fewer algebraic objects in the input.

Description

 • The GreatestCommonDivisor command computes the greatest common divisor of two (multivariate) polynomials whose coefficients contain radicals or RootOfs representing algebraic numbers.
 • The inputs a and b can be polynomials disguised as rational functions, in which case they are normalized first using Algebraic[Normal].
 • The inputs may even contain non-algebraic subexpressions such as $\mathrm{sin}\left(x\right)$ that are neither variables, numbers, or algebraic objects. These will be frozen and temporarily replaced by new local variables.
 • This command preserves partial factorizations in the input and expands polynomials only if necessary.
 • All non-constant factors in the gcd returned are monic with respect to a block-lexicographic ordering of the variables, where all global variables are considered larger than all local ones. If all variables have different names, then this ordering is session-independent.
 • All radicals and powers of RootOfs in the gcd returned are reduced with respect to their respective minimal polynomials.  That is, every radical is of the form ${a}^{r}$, where $0 is a rational number, and every integer exponent in a power of the form ${\mathrm{RootOf}\left(f,\mathrm{...}\right)}^{n}$ satisfies $0 .
 • Note that GreatestCommonDivisor cannot be used to compute the gcd of two constants, e.g., in the ring of integers of an algebraic number field. It returns $1$ for the gcd of two nonzero constants.
 • If the set of radicals and RootOfs in the inputs cannot be embedded into a field algebraically, the greatest common divisor may not always exist or may not be unique. GreatestCommonDivisor will try to find a field representation if there are at most $4$ algebraic objects in the input (unless option 'makeindependent' is given; see below), and otherwise attempt to compute a greatest common divisor anyway. If it does not succeed, it issues the error "reducible RootOf detected", unless the option 'symbolic'=true is given (see below).
 • If the optional arguments 'ca' and 'cb' are given, they are assigned the values of the cofactors $\frac{a}{g}$ and $\frac{b}{g}$, respectively, where $g$ is the gcd.
 • The cofactors are normalized as follows:
 – The leading coefficients, with respect to the same block-lexicographic ordering as described above, of all non-constant factors are positive integers (except possibly if there is only one non-constant factor).
 – There are at most two constant factors, and at most one of them is not a rational number.
 – All factors that are not rational numbers have integer content equal to $1$, except possibly if there is only one non-constant factor.
 – All radicals and powers of RootOfs are reduced with respect to their respective minimal polynomials, as described above.

Examples

 > with(Algebraic):

Introductory examples:

 > GreatestCommonDivisor(x^5+y^5,x^3+y^3);
 ${x}{+}{y}$ (1)
 > GreatestCommonDivisor(2*x^2*y+x^2-6*y-3, x^2-I*x*y-3^(1/2)*x+I*3^(1/2)*y);
 ${x}{-}\sqrt{{3}}$ (2)
 > a := (x+1)*(x+2)*(x/RootOf(_Z^2-2,index=1)+1):
 > b := x^2-2:
 > g := GreatestCommonDivisor(a,b,'ca','cb');
 ${g}{≔}{x}{+}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right)$ (3)
 > [ca,cb];
 $\left[\frac{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right){}\left({x}{+}{1}\right){}\left({x}{+}{2}\right)}{{2}}{,}{x}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{1}\right)\right]$ (4)
 > [Normal(a-ca*g),Normal(b-cb*g)];
 $\left[{0}{,}{0}\right]$ (5)

Polynomials disguised as rational functions are accepted, but true rational functions are not. Neither are algebraic functions or floating point numbers in the coefficients:

 > GreatestCommonDivisor((x^2-2)/(x+sqrt(2)),x^2-2*sqrt(2)*x+2);
 ${x}{-}\sqrt{{2}}$ (6)
 > GreatestCommonDivisor((x^2+2)/(x+sqrt(2)),x^2-2*sqrt(2)*x+2);
 > GreatestCommonDivisor(x^2-y,x^2+2*sqrt(y)*x+y);
 > GreatestCommonDivisor(x^2-2.0,x+sqrt(2));

Non-algebraic subexpressions are frozen and replaced by new variables:

 > GreatestCommonDivisor(x^2-3*cos(x)^2,x^2-2*sqrt(3)*x*cos(x)+3*cos(x)^2);
 ${-}{\mathrm{cos}}{}\left({x}\right){}\sqrt{{3}}{+}{x}$ (7)

Partial factorizations in the inputs are preserved:

 > a := (x^2-1)*(x^2-2):
 > b := (x^2+2*x+1)*(x-sqrt(2))^2:
 > [GreatestCommonDivisor(a,b,'ca','cb'),ca,cb];
 $\left[\left({x}{+}{1}\right){}\left({x}{-}\sqrt{{2}}\right){,}\left({x}{-}{1}\right){}\left({x}{+}\sqrt{{2}}\right){,}\left({x}{+}{1}\right){}\left({x}{-}\sqrt{{2}}\right)\right]$ (8)
 > [GreatestCommonDivisor(expand(a),expand(b),'ca','cb'),ca,cb];
 $\left[{{x}}^{{2}}{-}\sqrt{{2}}{}{x}{+}{x}{-}\sqrt{{2}}{,}{{x}}^{{2}}{+}\sqrt{{2}}{}{x}{-}{x}{-}\sqrt{{2}}{,}{{x}}^{{2}}{-}\sqrt{{2}}{}{x}{+}{x}{-}\sqrt{{2}}\right]$ (9)

The gcd of two nonzero constants is always $1$:

 > GreatestCommonDivisor(1+I,(1+I)^2);
 ${1}$ (10)

There is no way for GreatestCommonDivisor to know whether $\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right)$ without an index represents $\sqrt{2}$ or $-\sqrt{2}$. Option 'symbolic'=true picks $-\sqrt{2}$ in this case:

 > GreatestCommonDivisor(x-sqrt(2), x-RootOf(_Z^2-2,index=1));
 ${x}{-}\sqrt{{2}}$ (11)
 > GreatestCommonDivisor(x-sqrt(2), x-RootOf(_Z^2-2));
 > GreatestCommonDivisor(x-sqrt(2), x-RootOf(_Z^2-2),'symbolic'=true);
 ${1}$ (12)

An example where the gcd can be computed even though there is a non-indexed reducible RootOf:

 > GreatestCommonDivisor(x^2-1, x^2+2*RootOf(_Z^2-1)*x+1);
 ${x}{+}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{1}\right)$ (13)
 > GreatestCommonDivisor(x^2-1, x^2+2*RootOf(_Z^2-1,index=2)*x+1);
 ${x}{-}{1}$ (14)

Using option 'characteristic', gcds over finite fields can be computed:

 > GreatestCommonDivisor(x^2+1, x^2+x, 'characteristic'=2);
 ${x}{+}{1}$ (15)
 > GreatestCommonDivisor(x^2-6, x^2+2*I*x-1);
 ${1}$ (16)
 > GreatestCommonDivisor(x^2-6, x^2+2*I*x-1, 'characteristic'=7);
 ${x}{+}{I}$ (17)

In contrast to characteristic $0$, the complex number $I$, radicals, and indexed RootOfs are not uniquely defined in positive characteristic, and they are treated as if they were non-indexed RootOfs:

 > GreatestCommonDivisor(x-2, x-I, 'characteristic'='5');
 > GreatestCommonDivisor(x-2, x-I, 'characteristic'='5', 'symbolic'='true');
 ${1}$ (18)

The gcd cannot always be computed in composite characteristic:

 > GreatestCommonDivisor(x^2+1, x^2+9*x+8, 'characteristic'=65);
 ${x}{+}{8}$ (19)
 > GreatestCommonDivisor(x^2+1, x^2-4, 'characteristic'=65);

With option 'makeindependent'=true, the input will be checked for algebraic dependencies even if there are more than $4$ algebraic objects in the input:

 > CubeRootOf[-4]:=RootOf(_Z^3+4,index=1);
 ${{\mathrm{CubeRootOf}}}_{{-4}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{+}{4}{,}{\mathrm{index}}{=}{1}\right)$ (20)
 > CubeRootOf[-2]:=RootOf(_Z^3+2,index=1);
 ${{\mathrm{CubeRootOf}}}_{{-2}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{+}{2}{,}{\mathrm{index}}{=}{1}\right)$ (21)
 > CubeRootOf:=RootOf(_Z^3-2,index=1);
 ${{\mathrm{CubeRootOf}}}_{{2}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{2}{,}{\mathrm{index}}{=}{1}\right)$ (22)
 > CubeRootOf:=RootOf(_Z^3-3,index=1);
 ${{\mathrm{CubeRootOf}}}_{{3}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{3}{,}{\mathrm{index}}{=}{1}\right)$ (23)
 > CubeRootOf:=RootOf(_Z^3-4,index=1);
 ${{\mathrm{CubeRootOf}}}_{{4}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{4}{,}{\mathrm{index}}{=}{1}\right)$ (24)
 > CubeRootOf:=RootOf(_Z^3-6,index=1);
 ${{\mathrm{CubeRootOf}}}_{{6}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{6}{,}{\mathrm{index}}{=}{1}\right)$ (25)
 > GreatestCommonDivisor(x+CubeRootOf*CubeRootOf[-2]*CubeRootOf,x+CubeRootOf[-4]*CubeRootOf);
 > GreatestCommonDivisor(x+CubeRootOf*CubeRootOf[-2]*CubeRootOf,x+CubeRootOf[-4]*CubeRootOf,'makeindependent'=true);
 $\frac{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{+}{2}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{6}{,}{\mathrm{index}}{=}{1}\right){}{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{4}{,}{\mathrm{index}}{=}{1}\right)}^{{2}}}{{2}}{+}{x}$ (26)

With option 'makeindependent'=false, the input will never be checked for algebraic dependencies:

 > GreatestCommonDivisor(x+CubeRootOf*CubeRootOf,x+CubeRootOf,'makeindependent'=FAIL);
 ${x}{+}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{6}{,}{\mathrm{index}}{=}{1}\right)$ (27)
 > GreatestCommonDivisor(x+CubeRootOf*CubeRootOf,x+CubeRootOf,'makeindependent'=false);