FractionFreeRightEuclidean - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

OreTools[Modular]

 FractionFreeRightEucliean
 perform a fraction-free version of right Euclidean algorithm (usual, half-extended, and extended) modulo a prime
 RightEuclidean
 perform right Euclidean algorithm (usual, half-extended, and extended)

 Calling Sequence Modular[FractionFreeRightEuclidean](Poly1, Poly2, p, A, 'c1', 'c2') Modular[RightEuclidean](Poly1, Poly2, p, A, 'c1', 'c2')

Parameters

 Poly1, Poly2 - nonzero Ore polynomials; to define an Ore polynomial, use the OrePoly structure p - prime A - Ore algebra; to define an Ore algebra, use the SetOreRing command 'c1', 'c2' - (optional) unevaluated names

Description

 • Modular[FractionFreeRightEuclidean](Poly1, Poly2, p, A, 'c1', 'c2') calling sequence returns a list [m, S] where m is a positive integer and S is an array with m elements storing the subresultant sequence of the first kind of Poly1 and Poly2.
 The Modular[FractionFreeRightEuclidean] command requires that Poly1 and Poly2 be fraction-free, and that the commutation rule of the Ore algebra A also be fraction-free.
 • If the optional fourth argument to the FractionFreeRightEuclidean command c1 is specified, it is assigned the first co-sequence of Poly1 and Poly2 so that:

${\mathrm{c1}}_{i}\mathrm{Poly2}={S}_{i}\mathrm{mod Poly}1\mathrm{and}p,\left(i=1,2,\mathrm{...},m\right)$

 and c1[m+1] Poly2 is a least common left multiple (LCLM) of Poly1 and Poly2.
 • If the optional fifth argument to the FractionFreeRightEuclidean command c2 is specified, it is assigned the second co-sequence of Poly1 and Poly2 so that:

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

 and c1[m+1] Poly2 = - c2[m+1] Poly1 mod p is an LCLM of Poly1 and Poly2.
 • Modular[RightEuclidean](Poly1, Poly2, p, A, 'c1', 'c2') calling sequence returns a list [m, S] where m is a positive integer and S is an array with m elements storing the right Euclidean polynomial remainder sequence of Poly1 and Poly2.
 • If the optional fourth argument to the FractionFreeRightEuclidean command c1 is specified, it is assigned the first co-sequence of Poly1 and Poly2 so that:

${\mathrm{c1}}_{i}\mathrm{Poly2}={S}_{i}\mathrm{mod Poly}1\mathrm{and}p,\left(i=1,2,\mathrm{...},m\right)$

 and c1[m+1] Poly2 is a least common left multiple (LCLM) of Poly1 and Poly2.
 • If the optional fifth argument to the Modular[RightEuclidean] command c2 is specified, it is assigned the second co-sequence of Poly1 and Poly2 so that:

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

 and c1[m+1] Poly2 = - c2[m+1] Poly1 mod p is an LCLM 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)
 > $\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{Modular}\left[\mathrm{RightEuclidean}\right]\left(\mathrm{Ore1},\mathrm{Ore2},11,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}}{+}{10}{}{x}{+}{10}{,}{1}{+}{x}\right)& {\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)& {\mathrm{OrePoly}}{}\left(\frac{{10}{}{{x}}^{{5}}{+}{{x}}^{{4}}{+}{5}{}{{x}}^{{3}}{+}{7}{}{{x}}^{{2}}{+}{2}{}{x}}{{{x}}^{{4}}{+}{2}{}{{x}}^{{3}}{+}{3}{}{{x}}^{{2}}{+}{2}{}{x}{+}{1}}{,}\frac{{2}{}{{x}}^{{5}}{+}{5}{}{{x}}^{{4}}{+}{10}{}{{x}}^{{3}}{+}{8}{}{{x}}^{{2}}{+}{2}{}{x}{+}{10}}{{{x}}^{{4}}{+}{2}{}{{x}}^{{3}}{+}{3}{}{{x}}^{{2}}{+}{2}{}{x}{+}{1}}\right)& {\mathrm{OrePoly}}{}\left(\frac{{3}{}{{x}}^{{12}}{+}{4}{}{{x}}^{{11}}{+}{5}{}{{x}}^{{10}}{+}{{x}}^{{9}}{+}{8}{}{{x}}^{{8}}{+}{3}{}{{x}}^{{7}}{+}{8}{}{{x}}^{{6}}{+}{3}{}{{x}}^{{5}}{+}{6}{}{{x}}^{{4}}{+}{3}{}{{x}}^{{3}}{+}{6}{}{{x}}^{{2}}{+}{7}{}{x}{+}{6}}{{{x}}^{{10}}{+}{5}{}{{x}}^{{9}}{+}{8}{}{{x}}^{{8}}{+}{3}{}{{x}}^{{6}}{+}{7}{}{{x}}^{{4}}{+}{3}{}{{x}}^{{3}}{+}{8}{}{{x}}^{{2}}{+}{10}{}{x}{+}{3}}\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{Modular}\left[\mathrm{Multiply}\right]\left(\mathrm{c1}\left[i\right],\mathrm{Ore1},11,A\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{W2}≔\mathrm{Modular}\left[\mathrm{Multiply}\right]\left(\mathrm{c2}\left[i\right],\mathrm{Ore2},11,A\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}W≔\mathrm{Modular}\left[\mathrm{Add}\right]\left(\mathrm{W1},\mathrm{W2},11\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}C≔\mathrm{Modular}\left[\mathrm{Minus}\right]\left(W,S\left[i\right],11\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{Modular}\left[\mathrm{Multiply}\right]\left(\mathrm{c1}\left[5\right],\mathrm{Ore1},11,A\right):$
 > $\mathrm{W4}≔\mathrm{Modular}\left[\mathrm{Multiply}\right]\left(\mathrm{c2}\left[5\right],\mathrm{Ore2},11,A\right):$
 > $\mathrm{Modular}\left[\mathrm{Add}\right]\left(\mathrm{W3},\mathrm{W4},11\right)$
 ${\mathrm{OrePoly}}{}\left({0}\right)$ (8)

Try fraction-free right Euclidean algorithm.

 > $A≔\mathrm{SetOreRing}\left(x,'\mathrm{differential}'\right)$
 ${A}{≔}{\mathrm{UnivariateOreRing}}{}\left({x}{,}{\mathrm{differential}}\right)$ (9)
 > $\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)$ (10)
 > $\mathrm{Ore2}≔\mathrm{OrePoly}\left(x,x,{x}^{2}+x+1\right)$
 ${\mathrm{Ore2}}{≔}{\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)$ (11)
 > $U≔\mathrm{Modular}\left[\mathrm{FractionFreeRightEuclidean}\right]\left(\mathrm{Ore1},\mathrm{Ore2},11,A,'\mathrm{c1}','\mathrm{c2}'\right)$
 ${U}{≔}\left[{4}{,}{S}\right]$ (12)
 > $m≔U\left[1\right];$$S≔U\left[2\right]$
 ${m}{≔}{4}$
 ${S}{≔}{S}$ (13)
 > $\mathrm{print}\left(S\right)$
 $\left[\begin{array}{cccc}{\mathrm{OrePoly}}{}\left({1}{,}{3}{}{x}{,}{{x}}^{{2}}{+}{10}{}{x}{+}{10}{,}{1}{+}{x}\right)& {\mathrm{OrePoly}}{}\left({x}{,}{x}{,}{{x}}^{{2}}{+}{x}{+}{1}\right)& {\mathrm{OrePoly}}{}\left({10}{}{{x}}^{{5}}{+}{{x}}^{{4}}{+}{5}{}{{x}}^{{3}}{+}{7}{}{{x}}^{{2}}{+}{2}{}{x}{,}{2}{}{{x}}^{{5}}{+}{5}{}{{x}}^{{4}}{+}{10}{}{{x}}^{{3}}{+}{8}{}{{x}}^{{2}}{+}{2}{}{x}{+}{10}\right)& {\mathrm{OrePoly}}{}\left({{x}}^{{8}}{+}{3}{}{{x}}^{{7}}{+}{4}{}{{x}}^{{5}}{+}{6}{}{{x}}^{{4}}{+}{7}{}{{x}}^{{3}}{+}{3}{}{{x}}^{{2}}{+}{2}{}{x}{+}{2}\right)\end{array}\right]$ (14)

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{Modular}\left[\mathrm{Multiply}\right]\left(\mathrm{c1}\left[i\right],\mathrm{Ore1},11,A\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{W2}≔\mathrm{Modular}\left[\mathrm{Multiply}\right]\left(\mathrm{c2}\left[i\right],\mathrm{Ore2},11,A\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}W≔\mathrm{Modular}\left[\mathrm{Add}\right]\left(\mathrm{W1},\mathrm{W2},11\right);\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}C≔\mathrm{Modular}\left[\mathrm{Minus}\right]\left(W,S\left[i\right],11\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)$ (15)

Check the LCLM.

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

References

 Li, Z. "A subresultant theory for Ore polynomials with applications." Proc. of ISSAC'98, pp.132-139. Edited by O. Gloor. ACM Press, 1998.