Algebraic - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Algebraic

  

ExtendedEuclideanAlgorithm

  

extended Euclidean algorithm for polynomials with algebraic number coefficients

 

Calling Sequence

Parameters

Options

Description

Examples

Calling Sequence

ExtendedEuclideanAlgorithm(a, b, x, 's', 't', options)

Gcdex(a, b, x, 's', 't', options)

Parameters

a,b

-

polynomials in x with algebraic number coefficients

x

-

name

s, t

-

(optional) unevaluated names

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, ExtendedEuclideanAlgorithm 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 computation is performed over an extension of the ring 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 p is not a field, and the greatest common divisor may not exist or may not be unique.  ExtendedEuclideanAlgorithm will attempt to perform the computation 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 ExtendedEuclideanAlgorithm 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 ExtendedEuclideanAlgorithm command performs the extended Euclidean algorithm on a and b, polynomials in x. It computes and returns g, the greatest common divisor (gcd) of a and b, which is a monic polynomial in x. Additionally, the parameters `s` and `t`, if included, will be assigned the values of polynomials in x such that as+bt=g, where degrees&comma;x<degreeb&comma;x and degreet&comma;x<degreea&comma;x.

• 

The inputs a and b may contain algebraic number coefficients. These may be represented by radicals or with the RootOf notation (see type,algnum, type,radnum). In general, algebraic numbers will be returned in the same representation as they were received in. Nested radicals and RootOfs are also supported.  

• 

Note that ExtendedEuclideanAlgorithm cannot be used to perform the extended Euclidean algorithm on two constants, e.g., in the ring of integers. It returns 1 for the gcd of two nonzero constants. Use the igcdex command to perform the extended Euclidean algorithm on integers.

• 

The arguments a and b must be univariate polynomials in the variable x, which is typically a name. If other names or non-algebraic sub-expressions are included and they cannot be evaluated to algebraic numbers, an "unable to compute gcdex of multivariate polynomials" error will be returned.

• 

x can also be a function such as sinx, in which case it will be frozen and replaced by a new local variable. However, functions that are also of type AlgebraicObject such as sinπ3 will be converted to algebraic numbers before proceeding, so they cannot be treated as variables. Proceed with caution when using a function for x, as treating some functions as variables may produce mathematically unsound results.

• 

The inputs a and b can be polynomials disguised as rational functions, in which case they are normalized first using Algebraic[Normal].

• 

The output will be normalized as follows:

– 

All non-constant factors in the output are monic.

– 

The gcd will always be monic, and `s` and `t` will each contain at most two constant factors, only one of which may not be rational.

– 

All factors that are not rational numbers have integer content equal to 1, except possibly if there is only one non-constant factor.

– 

All algebraic numbers occurring in the results are reduced modulo their minimal polynomial (see Reduce), and all arguments of functions, if any, are normalized recursively (see Normal).

• 

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. ExtendedEuclideanAlgorithm 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 perform the computation anyway. If it does not succeed, it issues the error "reducible RootOf detected", unless the option 'symbolic'=true is given (see below).

• 

These functions do not support input containing floats or radical functions such as x.

Examples

withAlgebraic&colon;

Introductory examples:

ExtendedEuclideanAlgorithmx3+I&comma;x5I&comma;x&comma;s1&comma;t1

xI

(1)

s1&comma;t1

Ix31&comma;Ix

(2)

expandx3+Ix3I1+x5IxI

xI

(3)

r1RootOf_Z2_Z1

r1RootOf_Z2_Z1

(4)

ExtendedEuclideanAlgorithmx21r1&comma;x32r11&comma;x&comma;s2&comma;t2&comma;s2&comma;t2

xRootOf_Z2_Z1&comma;xRootOf_Z2_Z12x&comma;RootOf_Z2_Z1+2

(5)

The input may contain both radicals and RootOfs, and ExtendedEuclideanAlgorithm will embed the coefficients into an algebraic field, if possible:

ExtendedEuclideanAlgorithmx2+sqrt2x+RootOf_Z23&comma;index=1x+sqrt6&comma;x2+sqrt2x&comma;x&comma;s3&comma;t3&comma;s3&comma;t3

x+2&comma;33&comma;33

(6)

ExtendedEuclideanAlgorithmx2+sqrt2x+RootOf_Z23x+sqrt6&comma;x2+sqrt2x&comma;x&comma;s3&comma;t3&comma;s3&comma;t3

x+2&comma;RootOf_Z233&comma;RootOf_Z233

(7)

Nested and mixed radicals and RootOfs are handled as well:

ExtendedEuclideanAlgorithmx3RootOf_Z2RootOf_Z22&comma;index=1&comma;index=13&comma;x2sqrt2&comma;x&comma;s4&comma;t4&comma;s4&comma;t4

x214&comma;22&comma;2x2

(8)

The input must contain univariate polynomials only.  Multiple variables are not supported and an error will be returned:

ExtendedEuclideanAlgorithmx2+xy+y2+1&comma;x+y&comma;x

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) unable to compute gcdex of multivariate polynomials

This function does not perform the extended Euclidean algorithm over the integers. Use igcdex for that functionality:

ExtendedEuclideanAlgorithm24&comma;66&comma;x&comma;s5&comma;t5&comma;s5&comma;t5

1&comma;0&comma;166

(9)

igcdex24&comma;66&comma;s5&comma;t5&comma;s5&comma;t5

6&comma;3&comma;−1

(10)

The input can also be treated as a pair of polynomials in a non-algebraic sub-expression such as sinx, as it will be frozen and temporarily replaced by a new local variable:

ExtendedEuclideanAlgorithmsinx2+3sinx+2&comma;sinx2+4sinx+3&comma;sinx&comma;s7&comma;t7&comma;s7&comma;t7

sinx+1&comma;−1&comma;1

(11)

Other non-algebraic sub-expressions can only be included if they can be converted to algebraic numbers:

ExtendedEuclideanAlgorithmxtanπ4&comma;x+expIπ&comma;x&comma;s8&comma;t8&comma;s8&comma;t8

x1&comma;0&comma;1

(12)

ExtendedEuclideanAlgorithmx2siny2&comma;x2+2xsiny+siny2&comma;x

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) unable to compute gcdex of multivariate polynomials

Rational functions are generally not accepted, but polynomials disguised as rational functions are allowed, because they will be simplified by Normal:

ExtendedEuclideanAlgorithm1x&comma;1x2&comma;x

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) polynom(s) in x expected

ExtendedEuclideanAlgorithmx3x2Ix+Ix1&comma;x3+x2IxIx1&comma;x&comma;s9&comma;t9&comma;s9&comma;t9

x+1&comma;I2&comma;I2

(13)

The output will always be fully reduced and normalized (see Reduce, Normal):

ExtendedEuclideanAlgorithmx2RootOf_Z3_Z36&comma;x2+6x+2RootOf_Z3_Z3x+RootOf_Z3_Z36&comma;x

x+RootOf_Z3_Z3+3

(14)

Non-algebraic sub-expressions in the input may become algebraic after being recursively normalized:

ExtendedEuclideanAlgorithmx+sinπysqrt24yRootOf_Z22&comma;index=1&comma;x+sqrt22&comma;x

x+22

(15)

Floats are not accepted:

ExtendedEuclideanAlgorithmx2x+0.25&comma;x12&comma;x

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

Algebraic functions such as x are not accepted:

ExtendedEuclideanAlgorithmx2+2xsqrtx&comma;x+sqrtx&comma;x

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

When non-indexed RootOfs are given in the input, often the extended Euclidean Algorithm can still be performed and the answer expressed in terms of the input:

ExtendedEuclideanAlgorithmx22&comma;x3RootOf_Z28&comma;x&comma;s10&comma;t10&comma;s10&comma;t10

xRootOf_Z282&comma;x2&comma;12

(16)

However, in the following case, ExtendedEuclideanAlgorithm is unable to compute the gcd because it must know whether RootOf_Z22 represents 2 or 2 when no index is given. In such a case, it will return a "reducible RootOf detected" error:

ExtendedEuclideanAlgorithmx+sqrt2&comma;x+RootOf_Z22&comma;index=1&comma;x&comma;s11&comma;t11&comma;s11&comma;t11

x+2&comma;0&comma;1

(17)

ExtendedEuclideanAlgorithmx+sqrt2&comma;x+RootOf_Z22&comma;index=2&comma;x&comma;s12&comma;t12&comma;s12&comma;t12

1&comma;24&comma;24

(18)

ExtendedEuclideanAlgorithmx+sqrt2&comma;x+RootOf_Z22&comma;x

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) 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)}

By using option 'symbolic' = true, ExtendedEuclideanAlgorithm can be instructed to automatically select one of the possible substitutions and complete the computation.  Here, it picks RootOf_Z22=2:

ExtendedEuclideanAlgorithmx+sqrt2&comma;x+RootOf_Z22&comma;x&comma;s13&comma;t13&comma;symbolic=true&comma;s13&comma;t13

1&comma;24&comma;24

(19)

Using option 'characteristic', the extended gcd computation can be performed over finite fields:

ExtendedEuclideanAlgorithmx2+5&comma;x2+6x+2&comma;x&comma;s14&comma;t14&comma;characteristic=7&comma;s14&comma;t14

x+3&comma;1&comma;6

(20)

ExtendedEuclideanAlgorithmx2+2sqrt5x+5&comma;x2+6&comma;x&comma;s15&comma;t15&comma;characteristic=11&comma;s15&comma;t15

x+5&comma;105&comma;5

(21)

In composite characteristic, the gcd cannot always be computed. ExtendedEuclideanAlgorithm will return an error if it encounters a zero divisor:

ExtendedEuclideanAlgorithmx2+5x+6&comma;x2+3x+2&comma;x&comma;s16&comma;t16&comma;characteristic=9&comma;s16&comma;t16

x+2&comma;5&comma;4

(22)

ExtendedEuclideanAlgorithmx2+5x+6&comma;x2+3x+2&comma;x&comma;characteristic=10

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) zero divisor modulo 10 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:

CubeRootOf4RootOf_Z3+4&comma;index=1

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

(23)

CubeRootOf2RootOf_Z3+2&comma;index=1

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

(24)

CubeRootOf2RootOf_Z32&comma;index=1

CubeRootOf2RootOf_Z32&comma;index=1

(25)

CubeRootOf3RootOf_Z33&comma;index=1

CubeRootOf3RootOf_Z33&comma;index=1

(26)

CubeRootOf4RootOf_Z34&comma;index=1

CubeRootOf4RootOf_Z34&comma;index=1

(27)

CubeRootOf6RootOf_Z36&comma;index=1

CubeRootOf6RootOf_Z36&comma;index=1

(28)

ExtendedEuclideanAlgorithmx+CubeRootOf4CubeRootOf2CubeRootOf3&comma;x+CubeRootOf4CubeRootOf6&comma;x

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) 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))}

ExtendedEuclideanAlgorithmx+CubeRootOf4CubeRootOf2CubeRootOf3&comma;x+CubeRootOf4CubeRootOf6&comma;x&comma;makeindependent=true

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

(29)

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

ExtendedEuclideanAlgorithmx+CubeRootOf2CubeRootOf3&comma;x+CubeRootOf6&comma;x&comma;makeindependent=FAIL

x+RootOf_Z36&comma;index=1

(30)

ExtendedEuclideanAlgorithmx+CubeRootOf2CubeRootOf3&comma;x+CubeRootOf6&comma;x&comma;makeindependent=false

Error, (in Algebraic:-ExtendedEuclideanAlgorithm) 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[GreatestCommonDivisor]

Algebraic[Normal]

evala,Gcdex