Algebraic - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Algebraic

  

GreatestCommonDivisor

  

gcd of polynomials with algebraic number coefficients

 

Calling Sequence

Parameters

Options

Description

Examples

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 ringp 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 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 sinx 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 ar, where 0<r<1 is a rational number, and every integer exponent in a power of the form RootOff&comma;...n satisfies 0<n<degf .

• 

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 ag and bg, 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);

x3

(2)

a := (x+1)*(x+2)*(x/RootOf(_Z^2-2,index=1)+1):

b := x^2-2:

g := GreatestCommonDivisor(a,b,'ca','cb');

gx+RootOf_Z22&comma;index=1

(3)

[ca,cb];

RootOf_Z22&comma;index=1x+1x+22&comma;xRootOf_Z22&comma;index=1

(4)

[Normal(a-ca*g),Normal(b-cb*g)];

0&comma;0

(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);

x2

(6)

GreatestCommonDivisor((x^2+2)/(x+sqrt(2)),x^2-2*sqrt(2)*x+2);

Error, (in Algebraic:-GreatestCommonDivisor) polynom(s) with radalgnum coefficients expected

GreatestCommonDivisor(x^2-y,x^2+2*sqrt(y)*x+y);

Error, (in Algebraic:-GreatestCommonDivisor) polynom(s) with radalgnum coefficients expected

GreatestCommonDivisor(x^2-2.0,x+sqrt(2));

Error, (in Algebraic:-GreatestCommonDivisor) polynom(s) with radalgnum coefficients expected

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

cosx3+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];

x+1x2&comma;x1x+2&comma;x+1x2

(8)

[GreatestCommonDivisor(expand(a),expand(b),'ca','cb'),ca,cb];

x22x+x2&comma;x2+2xx2&comma;x22x+x2

(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 RootOf_Z22 without an index represents 2 or 2. Option 'symbolic'=true picks 2 in this case:

GreatestCommonDivisor(x-sqrt(2), x-RootOf(_Z^2-2,index=1));

x2

(11)

GreatestCommonDivisor(x-sqrt(2), x-RootOf(_Z^2-2));

Error, (in Algebraic:-GreatestCommonDivisor) reducible RootOf detected. Substitutions are {RootOf(_Z^2-2) = -RootOf(_Z^2-2,index = 1), RootOf(_Z^2-2) = RootOf(_Z^2-2,index = 1)}

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+RootOf_Z21

(13)

GreatestCommonDivisor(x^2-1, x^2+2*RootOf(_Z^2-1,index=2)*x+1);

x1

(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');

Error, (in Algebraic:-GreatestCommonDivisor) reducible RootOf detected. Substitutions are {RootOf(_Z^2+1,index = 1) = -3, RootOf(_Z^2+1,index = 1) = -2}

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

Error, (in Algebraic:-GreatestCommonDivisor) zero divisor modulo 65 detected

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

CubeRootOf−4RootOf_Z3+4&comma;index=1

(20)

CubeRootOf[-2]:=RootOf(_Z^3+2,index=1);

CubeRootOf−2RootOf_Z3+2&comma;index=1

(21)

CubeRootOf[2]:=RootOf(_Z^3-2,index=1);

CubeRootOf2RootOf_Z32&comma;index=1

(22)

CubeRootOf[3]:=RootOf(_Z^3-3,index=1);

CubeRootOf3RootOf_Z33&comma;index=1

(23)

CubeRootOf[4]:=RootOf(_Z^3-4,index=1);

CubeRootOf4RootOf_Z34&comma;index=1

(24)

CubeRootOf[6]:=RootOf(_Z^3-6,index=1);

CubeRootOf6RootOf_Z36&comma;index=1

(25)

GreatestCommonDivisor(x+CubeRootOf[4]*CubeRootOf[-2]*CubeRootOf[3],x+CubeRootOf[-4]*CubeRootOf[6]);

Error, (in Algebraic:-GreatestCommonDivisor) reducible RootOf detected. Substitutions are {RootOf(_Z^3+4,index = 1) = 1/2*RootOf(_Z^3-4,index = 1)^2*RootOf(_Z^3+2,index = 1), RootOf(_Z^3+4,index = 1) = RootOf(RootOf(_Z^3-4,index = 1)^2*RootOf(_Z^3+2,index = 1)*_Z-2*RootOf(_Z^3-4,index = 1)^2+2*_Z^2+4*RootOf(_Z^3+2,index = 1))}

GreatestCommonDivisor(x+CubeRootOf[4]*CubeRootOf[-2]*CubeRootOf[3],x+CubeRootOf[-4]*CubeRootOf[6],'makeindependent'=true);

RootOf_Z3+2&comma;index=1RootOf_Z36&comma;index=1RootOf_Z34&comma;index=122+x

(26)

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

GreatestCommonDivisor(x+CubeRootOf[2]*CubeRootOf[3],x+CubeRootOf[6],'makeindependent'=FAIL);

x+RootOf_Z36&comma;index=1

(27)

GreatestCommonDivisor(x+CubeRootOf[2]*CubeRootOf[3],x+CubeRootOf[6],'makeindependent'=false);

Error, (in Algebraic:-GreatestCommonDivisor) reducible RootOf detected. Substitutions are {RootOf(_Z^3-2,index = 1) = 1/3*RootOf(_Z^3-6,index = 1)*RootOf(_Z^3-3,index = 1)^2, RootOf(_Z^3-2,index = 1) = RootOf(RootOf(_Z^3-6,index = 1)*RootOf(_Z^3-3,index = 1)^2*_Z+RootOf(_Z^3-6,index = 1)^2*RootOf(_Z^3-3,index = 1)+3*_Z^2)}

See Also

Algebraic

Algebraic[Content]

Algebraic[ExtendedEuclideanAlgorithm]

Algebraic[Normal]

evala,Gcd