OreTools - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Algebra : Skew Polynomials : OreTools : OreTools/Euclidean

OreTools

  

Euclidean

  

perform right or left Euclidean algorithm

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

Euclidean['right'](Poly1, Poly2, A, 'c1', 'c2')

Euclidean(Poly1, Poly2, A, 'c1', 'c2')

Euclidean['left'](Poly1, Poly2, A, 'c1', 'c2')

Parameters

Poly1, Poly2

-

nonzero Ore polynomials; to define an Ore polynomial, use the OrePoly structure.

A

-

Ore algebra; to define an Ore algebra, use the SetOreRing function.

'c1', 'c2'

-

(optional) unevaluated names

Description

• 

The Euclidean['right'](Poly1, Poly2, A) or Euclidean(Poly1, Poly2, A) calling sequence returns a list [m, S] where m is a positive integer and S is an array with m nonzero Ore polynomials such that:

S1=Poly1,S2=Poly2,Si=Remainder'right'Si2,Si1,Ai=3,4,...,m.

  

In addition, Remainder['right'](S[m-1], S[m], A) = 0. S is called the right Euclidean polynomial remainder sequence of Poly1 and Poly2.

• 

If the fourth argument c1 of Euclidean['right'] or Euclidean is specified, it is assigned the first co-sequence of Poly1 and Poly2 so that:

c1iPoly1=Siisright divisiblebyPoly2,i=1,2,...,m

  

and c1[m+1] Poly1 is a least common left multiple (LCLM) of Poly1 and Poly2.

• 

If the fifth argument c2 of Euclidean['right'] or Euclidean is specified, it is assigned the second co-sequence of Poly1 and Poly2 so that:

c1iPoly1+c2iPoly2=Sii=1,2,...,m

  

and c1m+1Poly1=c2m+1Poly2 is an LCLM of Poly1 and Poly2.

• 

The Euclidean['left'](Poly1, Poly2, A) calling sequence returns a list [m, S] where m is a positive integer and S is an array with m nonzero Ore polynomials such that:

S1=Poly1,S2=Poly2,Si=Remainder'left'Si2,Si1,Ai=3,4,...,m.

  

In addition, Remainder['left']Sm1,Sm,A=0. S is called the left Euclidean polynomial remainder sequence of Poly1 and Poly2.

• 

If the fourth argument c1 of Euclidean['left'] is specified, it is assigned the first co-sequence of Poly1 and Poly2 so that:

Poly1c1iSiisleft divisiblebyPoly2,i=1,2,...,m

  

and Poly1 c1[m+1] is a least common right multiple (LCRM) of Poly1 and Poly2.

• 

If the fifth argument c2 of Euclidean['left'] is is specified, it is assigned the second co-sequence of Poly1 and Poly2 so that:

Poly1c1i+Poly2c2i=Sii=1,2,...,m

  

and Poly1 c1[m+1]= - Poly2 c2[m+1] is an LCRM of Poly1 and Poly2.

Examples

Perform the right Euclidean algorithm.

withOreTools:

ASetOreRingx,'differential'

A:=UnivariateOreRingx,differential

(1)

Ore1OrePoly1,3x,x21+x,23x+1

Ore1:=OrePoly1,3x,x2x1,23x+1

(2)

Ore2OrePolyx,x,x2+x+1

Ore2:=OrePolyx,x,x2+x+1

(3)

UEuclidean['right']Ore1,Ore2,A,'c1','c2'

U:=4,S

(4)

mU1;SU2

m:=4

S:=S

(5)

printS

OrePoly1,3x,x2x1,23x+1OrePolyx,x,x2+x+1OrePolyxx4x349x27x+20x2+x+12,2x517x4+32x314x220x1x2+x+12OrePolyx12+5x11200x10+598x9+1451x8+2135x7+1781x6+1343x5+1850x4+1420x3+981x25x202x517x4+32x314x220x12

(6)

Check the co-sequences.

foritomdoW1Multiplyc1i,Ore1,A;W2Multiplyc2i,Ore2,A;WAddW1,W2;CMinusW,Si;printCend do:

OrePoly0

OrePoly0

OrePoly0

OrePoly0

(7)

Check the LCLM.

W3Multiplyc15,Ore1,A:

W4Multiplyc25,Ore2,A:

AddW3,W4

OrePoly0

(8)

Perform the left Euclidean algorithm.

UEuclidean['left']Ore1,Ore2,A,'c1','c2'

U:=4,S

(9)

mU1;SU2

m:=4

S:=S

(10)

printS

OrePoly1,3x,x2x1,23x+1OrePolyx,x,x2+x+1OrePolyx7+18x5+99x412x31059x2955x51x2+x+13,2x521x4+20x317x2289x136x2+x+12OrePolyx12+x11+44x10+556x9+1037x8+1941x7+11909x6+36562x5+72548x4+88995x3+76169x2+39236x+123082x521x4+20x317x2289x1362

(11)

Check the co-sequences.

foritomdoW1MultiplyOre1,c1i,A;W2MultiplyOre2,c2i,A;WAddW1,W2;CMinusW,Si;printCend do:

OrePoly0

OrePoly0

OrePoly0

OrePoly0

(12)

Check the LCRM.

W3MultiplyOre1,c1m+1,A:

W4MultiplyOre2,c2m+1,A:

AddW3,W4

OrePoly0

(13)

See Also

OreTools

OreTools/Add

OreTools/Minus

OreTools/Multiply

OreTools/OreAlgebra

OreTools/OrePoly

OreTools/Quotient

OreTools/Remainder

OreTools[SetOreRing]

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam