compute greatest common right or left divisor (GCRD or GCLD) of Ore polynomials - Maple Help

# Online Help

###### All Products    Maple    MapleSim

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

OreTools[GCD] - compute greatest common right or left divisor (GCRD or GCLD) of Ore polynomials

OreTools[LCM] - compute least common left or right multiple (LCLM or LCRM) of Ore polynomials

OreTools[ExtendedGCD] - compute the GCRD or GCLD of two Ore polynomials and the last two members of the first or/and second co-sequences

 Calling Sequence GCD['right'](Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) GCD(Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) GCD['left'](Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) LCM['left'](Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) LCM(Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) LCM['right'](Poly1, Poly2, ..., Polyk, 'cofactors' = true, A) ExtendedGCD['right'](Poly1, Poly2, A, 'c1', 'c2') ExtendedGCD(Poly1, Poly2, A, 'c1', 'c2') ExtendedGCD['left'](Poly1, Poly2, A, 'c1', 'c2')

Parameters

 Poly1, Poly2, ..., Polyk - nonzero Ore polynomials; to define an Ore polynomial, use the OrePoly structure. 'cofactors' = true - (optional) equation; force computation of cofactors A - Ore algebra; to define an Ore algebra, use the SetOreRing function. c1, c2 - (optional) names.

Description

 • The GCD['right'](Poly1, Poly2, ..., Polyk, A) or GCD(Poly1, Poly2, ..., Polyk, A) calling sequence returns the monic GCRD of Poly1, Poly2, ..., Polyk. The GCD['left'](Poly1, Poly2, ..., Polyk, A) calling sequence returns the monic GCLD of Poly1, Poly2, ..., Polyk.
 If the optional 'cofactors = true' equation is specified, the GCD function returns a list in which the first element is the GCRD (resp. GCLD) of the Ore polynomials and the second element is a list of all the left (resp. right) cofactors of the Ore polynomials and the GCRD (resp. GCLD).
 • The LCM['left'](Poly1, Poly2, ..., Polyk, A) or LCM(Poly1, Poly2, ..., Polyk, A) calling sequence returns the monic LCLM of Poly1, Poly2, ..., Polyk. The LCM['right'](Poly1, Poly2, ..., Polyk, A) calling sequence returns the monic LCRM of Poly1, Poly2, ..., Polyk.
 If the optional 'cofactors = true' equation is specified, the LCM function returns a list in which the first element is the LCLM (resp. LCRM) of the Ore polynomials and the second element is a list of all the left (resp. right) cofactors of the LCLM (resp. LCRM) and the Ore polynomials.
 • The ExtendedGCD['right'](Poly1, Poly2, A) or ExtendedGCD(Poly1, Poly2, A) calling sequence returns the monic GCRD of Poly1 and Poly2.
 • The fourth optional argument c1, when present, is assigned a pair [u, v] of Ore polynomials such that (u Poly1 - G) is right divisible by Poly2, where G is the monic GCRD of Poly1 and Poly2; and v Poly1 is the LCLM of Poly1 and Poly2.
 • The fourth and fifth optional arguments c1 and c2, when present, are assigned two pairs [u1, v1] and [u2, v2] of Ore polynomials, respectively. In this case,

$\mathrm{u1}\mathrm{Poly1}+\mathrm{u2}\mathrm{Poly2}=G\mathrm{and}\mathrm{v1}\mathrm{Poly1}+\mathrm{v2}\mathrm{Poly2}=\mathrm{OrePoly}\left(0\right)$

 where G is the monic GCRD of Poly1 and Poly2, v1 Poly1 is the LCLM of Poly1 and Poly2.
 • The ExtendedGCD['left'](Poly1, Poly2, A) calling sequence returns the monic GCLD of Poly1 and Poly2.
 • The fourth optional argument c1, when present, is assigned a pair [u, v] of Ore polynomials such that (Poly1 u - G) is left divisible by Poly2, where G is the monic GCLD of Poly1 and Poly2; and Poly1 v is the LCRM of Poly1 and Poly2.
 • The fourth and fifth optional arguments c1 and c2, when present, are assigned two pairs [u1, v1] and [u2, v2] of Ore polynomials, respectively. In this case,

$\mathrm{Poly1}\mathrm{u1}+\mathrm{Poly2}\mathrm{u2}=G\mathrm{and}\mathrm{Poly1}\mathrm{v1}+\mathrm{Poly2}\mathrm{v2}=\mathrm{OrePoly}\left(0\right)$

 where G is the monic GCLD of Poly1 and Poly2, Poly1 v1 is the LCRM of Poly1 and Poly2.

Examples

 > $\mathrm{with}\left(\mathrm{OreTools}\right):$
 > $A:=\mathrm{SetOreRing}\left(x,'\mathrm{differential}'\right)$
 ${A}{:=}{\mathrm{UnivariateOreRing}}{}\left({x}{,}{\mathrm{differential}}\right)$ (1)
 > $G:=\mathrm{OrePoly}\left(1,3x\right)$
 ${G}{:=}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}\right)$ (2)
 > $\mathrm{Poly1}:=\mathrm{Multiply}\left(\mathrm{OrePoly}\left(\frac{1}{x},0,\frac{{x}^{2}}{x+2}\right),G,A\right)$
 ${\mathrm{Poly1}}{:=}{\mathrm{OrePoly}}{}\left(\frac{{1}}{{x}}{,}{3}{,}\frac{{7}{}{{x}}^{{2}}}{{x}{+}{2}}{,}\frac{{3}{}{{x}}^{{3}}}{{x}{+}{2}}\right)$ (3)
 > $\mathrm{Poly2}:=\mathrm{Multiply}\left(\mathrm{OrePoly}\left(x-1,x\right),G,A\right)$
 ${\mathrm{Poly2}}{:=}{\mathrm{OrePoly}}{}\left({x}{-}{1}{,}{3}{}{{x}}^{{2}}{+}{x}{,}{3}{}{{x}}^{{2}}\right)$ (4)
 > ${\mathrm{GCD}}_{'\mathrm{right}'}\left(\mathrm{Poly1},\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}{x}}{,}{1}\right)$ (5)
 > $\mathrm{GCD}\left(\mathrm{Poly1},G,\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}{x}}{,}{1}\right)$ (6)
 > $\mathrm{GCD}\left(\mathrm{Poly1},\mathrm{Poly2},G,'\mathrm{cofactors}=\mathrm{true}',A\right)$
 $\left[{\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}{x}}{,}{1}\right){,}\left[{\mathrm{OrePoly}}{}\left({3}{,}\frac{{6}{}{{x}}^{{2}}}{{x}{+}{2}}{,}\frac{{3}{}{{x}}^{{3}}}{{x}{+}{2}}\right){,}{\mathrm{OrePoly}}{}\left({3}{}{{x}}^{{2}}{,}{3}{}{{x}}^{{2}}\right){,}{\mathrm{OrePoly}}{}\left({3}{}{x}\right)\right]\right]$ (7)
 > $\mathrm{LCM}\left(\mathrm{Poly1},\mathrm{Poly2},G,A\right)$
 ${\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}}{}\frac{{{x}}^{{5}}{-}{3}{}{{x}}^{{4}}{-}{7}{}{{x}}^{{3}}{+}{15}{}{{x}}^{{2}}{-}{4}}{{{x}}^{{5}}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}{,}\frac{{1}}{{3}}{}\frac{{3}{}{{x}}^{{5}}{-}{5}{}{{x}}^{{4}}{-}{21}{}{{x}}^{{3}}{+}{33}{}{{x}}^{{2}}{+}{16}{}{x}{+}{4}}{{{x}}^{{4}}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}{,}\frac{{1}}{{3}}{}\frac{{7}{}{{x}}^{{5}}{-}{18}{}{{x}}^{{4}}{+}{7}{}{{x}}^{{3}}{+}{12}{}{{x}}^{{2}}{+}{40}{}{x}{+}{12}}{\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right){}{{x}}^{{3}}}{,}\frac{{1}}{{3}}{}\frac{{3}{}{{x}}^{{4}}{+}{{x}}^{{3}}{-}{17}{}{{x}}^{{2}}{+}{19}{}{x}{+}{32}}{{x}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}{,}{1}\right)$ (8)
 > $H:={\mathrm{ExtendedGCD}}_{'\mathrm{right}'}\left(\mathrm{Poly1},\mathrm{Poly2},A,'\mathrm{c1}'\right)$
 ${H}{:=}{\mathrm{OrePoly}}{}\left(\frac{{{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}}{{x}{}\left({x}{+}{2}\right)}{,}\frac{{3}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}{{x}{+}{2}}\right)$ (9)
 > $\mathrm{c1}$
 $\left[{\mathrm{OrePoly}}{}\left({1}\right){,}{\mathrm{OrePoly}}{}\left({-}\frac{{{x}}^{{2}}{}\left({{x}}^{{4}}{-}{2}{}{{x}}^{{3}}{-}{7}{}{{x}}^{{2}}{+}{12}{}{x}{+}{4}\right)}{{\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}^{{2}}}{,}{-}\frac{{{x}}^{{2}}{}\left({x}{+}{2}\right)}{{{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}}\right)\right]$ (10)

Check result.

 > ${\mathrm{Remainder}}_{'\mathrm{right}'}\left(\mathrm{Minus}\left(\mathrm{Multiply}\left({\mathrm{c1}}_{1},\mathrm{Poly1},A\right),H\right),\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (11)
 > $\mathrm{Remainder}\left(\mathrm{Multiply}\left({\mathrm{c1}}_{2},\mathrm{Poly1},A\right),\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (12)
 > $H:=\mathrm{ExtendedGCD}\left(\mathrm{Poly1},\mathrm{Poly2},A,'\mathrm{c1}','\mathrm{c2}'\right)$
 ${H}{:=}{\mathrm{OrePoly}}{}\left(\frac{{{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}}{{x}{}\left({x}{+}{2}\right)}{,}\frac{{3}{}\left({{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{x}{+}{2}\right)}{{x}{+}{2}}\right)$ (13)

Check result.

 > $\mathrm{Minus}\left(\mathrm{Add}\left(\mathrm{Multiply}\left({\mathrm{c1}}_{1},\mathrm{Poly1},A\right),\mathrm{Multiply}\left({\mathrm{c2}}_{1},\mathrm{Poly2},A\right)\right),H\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (14)
 > $\mathrm{Add}\left(\mathrm{Multiply}\left({\mathrm{c1}}_{2},\mathrm{Poly1},A\right),\mathrm{Multiply}\left({\mathrm{c2}}_{2},\mathrm{Poly2},A\right)\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (15)
 > $A:=\mathrm{SetOreRing}\left(n,'\mathrm{shift}'\right)$
 ${A}{:=}{\mathrm{UnivariateOreRing}}{}\left({n}{,}{\mathrm{shift}}\right)$ (16)
 > $G:=\mathrm{OrePoly}\left(1,3n-3\right)$
 ${G}{:=}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{n}{-}{3}\right)$ (17)
 > $\mathrm{Poly1}:=\mathrm{Multiply}\left(G,\mathrm{OrePoly}\left(1,n,{n}^{2}\right),A\right)$
 ${\mathrm{Poly1}}{:=}{\mathrm{OrePoly}}{}\left({1}{,}{4}{}{n}{-}{3}{,}{4}{}{{n}}^{{2}}{-}{3}{,}{3}{}\left({n}{-}{1}\right){}{\left({n}{+}{1}\right)}^{{2}}\right)$ (18)
 > $\mathrm{Poly2}:=\mathrm{Multiply}\left(G,\mathrm{OrePoly}\left(n-1,n\right),G,A\right)$
 ${\mathrm{Poly2}}{:=}{\mathrm{OrePoly}}{}\left({n}{-}{1}{,}{6}{}{{n}}^{{2}}{-}{8}{}{n}{+}{3}{,}{9}{}{{n}}^{{3}}{-}{3}{}{{n}}^{{2}}{-}{3}{,}{9}{}\left({n}{-}{1}\right){}{\left({n}{+}{1}\right)}^{{2}}\right)$ (19)
 > ${\mathrm{GCD}}_{'\mathrm{left}'}\left(\mathrm{Poly1},\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}\left({n}{-}{2}\right)}{,}{1}\right)$ (20)
 > ${\mathrm{GCD}}_{'\mathrm{left}'}\left(\mathrm{Poly1},\mathrm{Poly2},G,'\mathrm{cofactors}=\mathrm{true}',A\right)$
 $\left[{\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}\left({n}{-}{2}\right)}{,}{1}\right){,}\left[{\mathrm{OrePoly}}{}\left({3}{}{n}{-}{6}{,}{3}{}{{n}}^{{2}}{-}{6}{}{n}{,}{3}{}\left({n}{-}{2}\right){}{{n}}^{{2}}\right){,}{\mathrm{OrePoly}}{}\left({3}{}{{n}}^{{2}}{-}{9}{}{n}{+}{6}{,}{9}{}{{n}}^{{3}}{-}{33}{}{{n}}^{{2}}{+}{39}{}{n}{-}{18}{,}{9}{}\left({n}{-}{2}\right){}{{n}}^{{2}}\right){,}{\mathrm{OrePoly}}{}\left({3}{}{n}{-}{6}\right)\right]\right]$ (21)
 > ${\mathrm{LCM}}_{'\mathrm{right}'}\left(\mathrm{Poly1},\mathrm{Poly2},G,A\right)$
 ${\mathrm{OrePoly}}{}\left(\frac{{1}}{{9}}{}\frac{{7}{}{{n}}^{{3}}{-}{66}{}{{n}}^{{2}}{+}{176}{}{n}{-}{117}}{{7}{}{{n}}^{{7}}{-}{171}{}{{n}}^{{6}}{+}{1750}{}{{n}}^{{5}}{-}{9735}{}{{n}}^{{4}}{+}{31813}{}{{n}}^{{3}}{-}{61104}{}{{n}}^{{2}}{+}{63900}{}{n}{-}{28080}}{,}\frac{{1}}{{9}}{}\frac{{49}{}{{n}}^{{5}}{-}{518}{}{{n}}^{{4}}{+}{1972}{}{{n}}^{{3}}{-}{3307}{}{{n}}^{{2}}{+}{2398}{}{n}{-}{648}}{\left({{n}}^{{5}}{-}{15}{}{{n}}^{{4}}{+}{87}{}{{n}}^{{3}}{-}{245}{}{{n}}^{{2}}{+}{336}{}{n}{-}{180}\right){}\left({7}{}{{n}}^{{3}}{-}{38}{}{{n}}^{{2}}{+}{58}{}{n}{-}{27}\right)}{,}\frac{{2}}{{9}}{}\frac{{56}{}{{n}}^{{5}}{-}{297}{}{{n}}^{{4}}{+}{430}{}{{n}}^{{3}}{-}{141}{}{{n}}^{{2}}{+}{48}{}{n}{-}{81}}{\left({{n}}^{{3}}{-}{8}{}{{n}}^{{2}}{+}{20}{}{n}{-}{16}\right){}{n}{}\left({7}{}{{n}}^{{2}}{-}{17}{}{n}{+}{3}\right){}\left({n}{-}{1}\right)}{,}\frac{{1}}{{9}}{}\frac{{105}{}{{n}}^{{5}}{-}{122}{}{{n}}^{{4}}{-}{291}{}{{n}}^{{3}}{+}{260}{}{{n}}^{{2}}{+}{171}{}{n}{-}{144}}{\left({{n}}^{{3}}{-}{5}{}{{n}}^{{2}}{+}{7}{}{n}{-}{3}\right){}{n}{}\left({7}{}{{n}}^{{2}}{-}{3}{}{n}{-}{7}\right)}{,}\frac{{1}}{{3}}{}\frac{{21}{}{{n}}^{{5}}{+}{47}{}{{n}}^{{4}}{-}{8}{}{{n}}^{{3}}{-}{70}{}{{n}}^{{2}}{+}{4}{}{n}{+}{21}}{\left({n}{-}{2}\right){}\left({7}{}{{n}}^{{2}}{+}{11}{}{n}{-}{3}\right){}{{n}}^{{2}}}{,}{1}\right)$ (22)
 > $H:={\mathrm{ExtendedGCD}}_{'\mathrm{left}'}\left(\mathrm{Poly1},\mathrm{Poly2},A,'\mathrm{c1}'\right)$
 ${H}{:=}{\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}\left({n}{-}{2}\right)}{,}{1}\right)$ (23)
 > $\mathrm{c1}$
 $\left[{\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}}{}\frac{{9}{}{{n}}^{{4}}{-}{96}{}{{n}}^{{3}}{+}{373}{}{{n}}^{{2}}{-}{633}{}{n}{+}{401}}{{7}{}{{n}}^{{5}}{-}{94}{}{{n}}^{{4}}{+}{492}{}{{n}}^{{3}}{-}{1259}{}{{n}}^{{2}}{+}{1580}{}{n}{-}{780}}{,}\frac{{3}{}{{n}}^{{2}}{-}{8}{}{n}{+}{3}}{{7}{}{{n}}^{{3}}{-}{45}{}{{n}}^{{2}}{+}{89}{}{n}{-}{54}}\right){,}{\mathrm{OrePoly}}{}\left(\frac{{1}}{{27}}{}\frac{\left({9}{}{{n}}^{{5}}{-}{111}{}{{n}}^{{4}}{+}{517}{}{{n}}^{{3}}{-}{1129}{}{{n}}^{{2}}{+}{1148}{}{n}{-}{434}\right){}\left({3}{}{{n}}^{{2}}{-}{14}{}{n}{+}{14}\right){}\left({3}{}{{n}}^{{2}}{-}{20}{}{n}{+}{31}\right)}{\left({7}{}{{n}}^{{4}}{-}{80}{}{{n}}^{{3}}{+}{332}{}{{n}}^{{2}}{-}{595}{}{n}{+}{390}\right){}\left({7}{}{{n}}^{{5}}{-}{94}{}{{n}}^{{4}}{+}{492}{}{{n}}^{{3}}{-}{1259}{}{{n}}^{{2}}{+}{1580}{}{n}{-}{780}\right)}{,}\frac{{1}}{{27}}{}\frac{\left({21}{}{{n}}^{{4}}{-}{212}{}{{n}}^{{3}}{+}{762}{}{{n}}^{{2}}{-}{1165}{}{n}{+}{648}\right){}{\left({3}{}{{n}}^{{2}}{-}{8}{}{n}{+}{3}\right)}^{{2}}{}{\left({3}{}{{n}}^{{2}}{-}{14}{}{n}{+}{14}\right)}^{{2}}}{\left({7}{}{{n}}^{{4}}{-}{80}{}{{n}}^{{3}}{+}{332}{}{{n}}^{{2}}{-}{595}{}{n}{+}{390}\right){}\left({7}{}{{n}}^{{2}}{-}{31}{}{n}{+}{27}\right){}\left({7}{}{{n}}^{{5}}{-}{59}{}{{n}}^{{4}}{+}{186}{}{{n}}^{{3}}{-}{277}{}{{n}}^{{2}}{+}{197}{}{n}{-}{54}\right)}{,}\frac{{1}}{{9}}{}\frac{{\left({3}{}{{n}}^{{2}}{-}{2}{}{n}{-}{2}\right)}^{{2}}{}{\left({3}{}{{n}}^{{2}}{-}{8}{}{n}{+}{3}\right)}^{{2}}}{\left({7}{}{{n}}^{{2}}{-}{17}{}{n}{+}{3}\right){}{{n}}^{{2}}{}\left({7}{}{{n}}^{{3}}{-}{45}{}{{n}}^{{2}}{+}{89}{}{n}{-}{54}\right)}\right)\right]$ (24)

Check result.

 > ${\mathrm{Remainder}}_{'\mathrm{left}'}\left(\mathrm{Minus}\left(\mathrm{Multiply}\left(\mathrm{Poly1},{\mathrm{c1}}_{1},A\right),H\right),\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (25)
 > ${\mathrm{Remainder}}_{'\mathrm{left}'}\left(\mathrm{Multiply}\left(\mathrm{Poly1},{\mathrm{c1}}_{2},A\right),\mathrm{Poly2},A\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (26)
 > $H:={\mathrm{ExtendedGCD}}_{'\mathrm{left}'}\left(\mathrm{Poly1},\mathrm{Poly2},A,'\mathrm{c1}','\mathrm{c2}'\right)$
 ${H}{:=}{\mathrm{OrePoly}}{}\left(\frac{{1}}{{3}{}\left({n}{-}{2}\right)}{,}{1}\right)$ (27)

Check result.

 > $\mathrm{Minus}\left(\mathrm{Add}\left(\mathrm{Multiply}\left(\mathrm{Poly1},{\mathrm{c1}}_{1},A\right),\mathrm{Multiply}\left(\mathrm{Poly2},{\mathrm{c2}}_{1},A\right)\right),H\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (28)
 > $\mathrm{Add}\left(\mathrm{Multiply}\left(\mathrm{Poly1},{\mathrm{c1}}_{2},A\right),\mathrm{Multiply}\left(\mathrm{Poly2},{\mathrm{c2}}_{2},A\right)\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (29)
 See Also

References

 Abramov, S.A.; Le, H.Q.; and Li, Z. "OreTools: a computer algebra library for univariate Ore polynomial rings." Technical Report CS-2003-12. School of Computer Science, University of Waterloo, 2003.
 Li, Z., and Nemes, I. "A modular algorithm for computing greatest common right divisors of Ore polynomials." Proc. of ISSAC'97, pp. 282-289. Edited by W. Kuechlin. ACM Press, 1997.

## Was this information helpful?

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