OreTools - Maple Programming Help

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

OreTools

 Euclidean
 perform right or left Euclidean algorithm

 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:

${S}_{1}=\mathrm{Poly1},{S}_{2}=\mathrm{Poly2},{S}_{i}={\mathrm{Remainder}}_{'\mathrm{right}'}\left({S}_{i-2},{S}_{i-1},A\right)\left(i=3,4,\mathrm{...},m\right).$

 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:

${\mathrm{c1}}_{i}\mathrm{Poly1}={S}_{i}\mathrm{is}\mathrm{right divisible}\mathrm{by}\mathrm{Poly2},\left(i=1,2,\mathrm{...},m\right)$

 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:

${\mathrm{c1}}_{i}\mathrm{Poly1}+{\mathrm{c2}}_{i}\mathrm{Poly2}={S}_{i}\left(i=1,2,\mathrm{...},m\right)$

 and ${\mathrm{c1}}_{m+1}\mathrm{Poly1}=-{\mathrm{c2}}_{m+1}\mathrm{Poly2}$ 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:

${S}_{1}=\mathrm{Poly1},{S}_{2}=\mathrm{Poly2},{S}_{i}={\mathrm{Remainder}}_{'\mathrm{left}'}\left({S}_{i-2},{S}_{i-1},A\right)\left(i=3,4,\mathrm{...},m\right).$

 In addition, ${\mathrm{Remainder}}_{'\mathrm{left}'}\left({S}_{m-1},{S}_{m},A\right)=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:

$\mathrm{Poly1}{\mathrm{c1}}_{i}-{S}_{i}\mathrm{is}\mathrm{left divisible}\mathrm{by}\mathrm{Poly2},\left(i=1,2,\mathrm{...},m\right)$

 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:

$\mathrm{Poly1}{\mathrm{c1}}_{i}+\mathrm{Poly2}{\mathrm{c2}}_{i}={S}_{i}\left(i=1,2,\mathrm{...},m\right)$

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

Examples

Perform the right Euclidean algorithm.

 > $\mathrm{with}\left(\mathrm{OreTools}\right):$
 > $A≔\mathrm{SetOreRing}\left(x,'\mathrm{differential}'\right)$
 ${A}{≔}{\mathrm{UnivariateOreRing}}{}\left({x}{,}{\mathrm{differential}}\right)$ (1)
 > $\mathrm{Ore1}≔\mathrm{OrePoly}\left(1,3x,{x}^{2}-\left(1+x\right),23x+1\right)$
 ${\mathrm{Ore1}}{≔}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}{,}{{x}}^{{2}}{-}{x}{-}{1}{,}{23}{}{x}{+}{1}\right)$ (2)
 > $\mathrm{Ore2}≔\mathrm{OrePoly}\left(x,x,{x}^{2}+x+1\right)$
 ${\mathrm{Ore2}}{≔}{\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)$ (3)
 > $U≔\mathrm{Euclidean}\left['\mathrm{right}'\right]\left(\mathrm{Ore1},\mathrm{Ore2},A,'\mathrm{c1}','\mathrm{c2}'\right)$
 ${U}{≔}\left[{4}{,}{S}\right]$ (4)
 > $m≔U\left[1\right];$$S≔U\left[2\right]$
 ${m}{≔}{4}$
 ${S}{≔}{S}$ (5)
 > $\mathrm{print}\left(S\right)$
 $\left[\begin{array}{cccc}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}{,}{{x}}^{{2}}{-}{x}{-}{1}{,}{23}{}{x}{+}{1}\right)& {\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)& {\mathrm{OrePoly}}{}\left({-}\frac{{x}{}\left({{x}}^{{4}}{-}{{x}}^{{3}}{-}{49}{}{{x}}^{{2}}{-}{7}{}{x}{+}{20}\right)}{{\left({{x}}^{{2}}{+}{x}{+}{1}\right)}^{{2}}}{,}\frac{{2}{}{{x}}^{{5}}{-}{17}{}{{x}}^{{4}}{+}{32}{}{{x}}^{{3}}{-}{14}{}{{x}}^{{2}}{-}{20}{}{x}{-}{1}}{{\left({{x}}^{{2}}{+}{x}{+}{1}\right)}^{{2}}}\right)& {\mathrm{OrePoly}}{}\left(\frac{{{x}}^{{12}}{+}{5}{}{{x}}^{{11}}{-}{200}{}{{x}}^{{10}}{+}{598}{}{{x}}^{{9}}{+}{1451}{}{{x}}^{{8}}{+}{2135}{}{{x}}^{{7}}{+}{1781}{}{{x}}^{{6}}{+}{1343}{}{{x}}^{{5}}{+}{1850}{}{{x}}^{{4}}{+}{1420}{}{{x}}^{{3}}{+}{981}{}{{x}}^{{2}}{-}{5}{}{x}{-}{20}}{{\left({2}{}{{x}}^{{5}}{-}{17}{}{{x}}^{{4}}{+}{32}{}{{x}}^{{3}}{-}{14}{}{{x}}^{{2}}{-}{20}{}{x}{-}{1}\right)}^{{2}}}\right)\end{array}\right]$ (6)

Check the co-sequences.

 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}m\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{W1}≔\mathrm{Multiply}\left(\mathrm{c1}\left[i\right],\mathrm{Ore1},A\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{W2}≔\mathrm{Multiply}\left(\mathrm{c2}\left[i\right],\mathrm{Ore2},A\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}W≔\mathrm{Add}\left(\mathrm{W1},\mathrm{W2}\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}C≔\mathrm{Minus}\left(W,S\left[i\right]\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{print}\left(C\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (7)

Check the LCLM.

 > $\mathrm{W3}≔\mathrm{Multiply}\left(\mathrm{c1}\left[5\right],\mathrm{Ore1},A\right):$
 > $\mathrm{W4}≔\mathrm{Multiply}\left(\mathrm{c2}\left[5\right],\mathrm{Ore2},A\right):$
 > $\mathrm{Add}\left(\mathrm{W3},\mathrm{W4}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (8)

Perform the left Euclidean algorithm.

 > $U≔\mathrm{Euclidean}\left['\mathrm{left}'\right]\left(\mathrm{Ore1},\mathrm{Ore2},A,'\mathrm{c1}','\mathrm{c2}'\right)$
 ${U}{≔}\left[{4}{,}{S}\right]$ (9)
 > $m≔U\left[1\right];$$S≔U\left[2\right]$
 ${m}{≔}{4}$
 ${S}{≔}{S}$ (10)
 > $\mathrm{print}\left(S\right)$
 $\left[\begin{array}{cccc}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}{,}{{x}}^{{2}}{-}{x}{-}{1}{,}{23}{}{x}{+}{1}\right)& {\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)& {\mathrm{OrePoly}}{}\left({-}\frac{{{x}}^{{7}}{+}{18}{}{{x}}^{{5}}{+}{99}{}{{x}}^{{4}}{-}{12}{}{{x}}^{{3}}{-}{1059}{}{{x}}^{{2}}{-}{955}{}{x}{-}{51}}{{\left({{x}}^{{2}}{+}{x}{+}{1}\right)}^{{3}}}{,}\frac{{2}{}{{x}}^{{5}}{-}{21}{}{{x}}^{{4}}{+}{20}{}{{x}}^{{3}}{-}{17}{}{{x}}^{{2}}{-}{289}{}{x}{-}{136}}{{\left({{x}}^{{2}}{+}{x}{+}{1}\right)}^{{2}}}\right)& {\mathrm{OrePoly}}{}\left(\frac{{{x}}^{{12}}{+}{{x}}^{{11}}{+}{44}{}{{x}}^{{10}}{+}{556}{}{{x}}^{{9}}{+}{1037}{}{{x}}^{{8}}{+}{1941}{}{{x}}^{{7}}{+}{11909}{}{{x}}^{{6}}{+}{36562}{}{{x}}^{{5}}{+}{72548}{}{{x}}^{{4}}{+}{88995}{}{{x}}^{{3}}{+}{76169}{}{{x}}^{{2}}{+}{39236}{}{x}{+}{12308}}{{\left({2}{}{{x}}^{{5}}{-}{21}{}{{x}}^{{4}}{+}{20}{}{{x}}^{{3}}{-}{17}{}{{x}}^{{2}}{-}{289}{}{x}{-}{136}\right)}^{{2}}}\right)\end{array}\right]$ (11)

Check the co-sequences.

 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}m\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{W1}≔\mathrm{Multiply}\left(\mathrm{Ore1},\mathrm{c1}\left[i\right],A\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{W2}≔\mathrm{Multiply}\left(\mathrm{Ore2},\mathrm{c2}\left[i\right],A\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}W≔\mathrm{Add}\left(\mathrm{W1},\mathrm{W2}\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}C≔\mathrm{Minus}\left(W,S\left[i\right]\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{print}\left(C\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (12)

Check the LCRM.

 > $\mathrm{W3}≔\mathrm{Multiply}\left(\mathrm{Ore1},\mathrm{c1}\left[m+1\right],A\right):$
 > $\mathrm{W4}≔\mathrm{Multiply}\left(\mathrm{Ore2},\mathrm{c2}\left[m+1\right],A\right):$
 > $\mathrm{Add}\left(\mathrm{W3},\mathrm{W4}\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (13)