Gcd - Maple Programming Help

Home : Support : Online Help : Mathematics : Evaluation : evala : evala/Gcd

Gcd

Greatest common divisor of polynomials over algebraic extensions

 Calling Sequence evala(Gcd(P, Q, 'p', 'q'), opts)

Parameters

 P, Q - polynomials over an algebraic number or function field. p, q - (optional) names opts - (optional) an option name or a set of option names. - Options currently supported: 'independent'.

Description

 • This function computes the monic greatest common divisor of two polynomials with coefficients in an algebraic function field or an algebraic number field.
 Since the ordering of objects may vary from a session to another, the leading coefficient may change accordingly.
 • Algebraic functions and algebraic numbers may be represented by radicals or with the RootOf notation (see type,algnum, type,algfun, type,radnum, type,radfun).
 • The optional arguments p and q are respectively assigned the co-factors of P and Q. Namely, $p=\frac{P}{G}$, $q=\frac{Q}{G}$ where G is the Gcd.
 • The computation is performed in the domain ${K}_{x}$, where:
 x is the set of names in P and Q which do not appear inside a RootOf or a radical,
 K is a field generated over the rational numbers by the coefficients of P and Q.
 The arguments P and Q must be polynomials in x.
 • Partial factorizations are preserved. The result may be a product of powers of expanded polynomials.
 • Algebraic numbers and functions occurring in the results are reduced modulo their minimal polynomial (see Normal).
 • If the RootOf and the radicals defining the algebraic numbers are not independent, a case discussion T of the gcd of P and Q over the direct product of rings F defined by the towers of algebraic extensions is computed first. Then, the result of T is combined. If the gcd values over all the branches of T can be combined into one, namely G, then G is the output. Otherwise, an error is reported.
 • If the expression contains only algebraic numbers in radical notation (2^(1/2), 3^(1/2), 6^(1/2)), the algebraic quantities are not necessarily independent. A basis over Q for the radicals can be computed by Maple in this case.
 • To skip the independence checking, use the option 'independent'. However, if a zero-divisor is hit when normalizing P and Q during the computation, an error is reported. Furthermore, the result may be incorrect if the option 'independent' is used but the RootOfs are not actually independent.
 • If a or b contains functions, their arguments are normalized recursively and the functions are frozen before the computation proceeds.
 • Other objects are frozen and considered as variables.

Examples

 > $\mathrm{alias}\left(\mathrm{α}=\mathrm{RootOf}\left({x}^{3}+x+1\right)\right)$
 ${\mathrm{α}}$ (1)
 > $\mathrm{P1}≔\left(x-\mathrm{α}\right){\left({x}^{2}-{\mathrm{α}}^{2}\right)}^{2}\left(x-1\right)$
 ${\mathrm{P1}}{≔}\left({x}{-}{\mathrm{α}}\right){}{\left({-}{{\mathrm{α}}}^{{2}}{+}{{x}}^{{2}}\right)}^{{2}}{}\left({x}{-}{1}\right)$ (2)
 > $\mathrm{Q1}≔\mathrm{evala}\left(\mathrm{Expand}\left({\left(x+\mathrm{α}\right)}^{3}\right)\right)$
 ${\mathrm{Q1}}{≔}{-}{\mathrm{α}}{-}{1}{+}{3}{}{{\mathrm{α}}}^{{2}}{}{x}{+}{3}{}{\mathrm{α}}{}{{x}}^{{2}}{+}{{x}}^{{3}}$ (3)
 > $\mathrm{G1}≔\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P1},\mathrm{Q1},'\mathrm{p1}','\mathrm{q1}'\right)\right)$
 ${\mathrm{G1}}{≔}{\left({x}{+}{\mathrm{α}}\right)}^{{2}}$ (4)
 > $\mathrm{p1}$
 ${\left({x}{-}{\mathrm{α}}\right)}^{{3}}{}\left({x}{-}{1}\right)$ (5)
 > $\mathrm{q1}$
 ${x}{+}{\mathrm{α}}$ (6)
 > $\mathrm{P2}≔\left(x-\sqrt{t}y\right){\left(\sqrt{t}x+1\right)}^{2}$
 ${\mathrm{P2}}{≔}\left({x}{-}\sqrt{{t}}{}{y}\right){}{\left(\sqrt{{t}}{}{x}{+}{1}\right)}^{{2}}$ (7)
 > $\mathrm{Q2}≔\mathrm{expand}\left(\frac{\partial }{\partial x}\mathrm{P2}\right)$
 ${\mathrm{Q2}}{≔}{3}{}{t}{}{{x}}^{{2}}{+}{4}{}\sqrt{{t}}{}{x}{+}{1}{-}{2}{}{{t}}^{{3}{/}{2}}{}{y}{}{x}{-}{2}{}{t}{}{y}$ (8)
 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P2},\mathrm{Q2}\right)\right)$
 ${x}{+}\frac{{1}}{\sqrt{{t}}}$ (9)

The second argument below is not a polynomial. Therefore, an error is returned:

 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P2},\mathrm{Q2}+\frac{1}{x}\right)\right)$

If a polynomial defining a RootOf is reducible, the RootOf does not generate a well-defined field. The command computes a case discussion and then tries to combine the result. In some cases, an error is returned, as described above.

 > ${\mathrm{infolevel}}_{\mathrm{Gcd}}≔1$
 ${{\mathrm{infolevel}}}_{{\mathrm{Gcd}}}{≔}{1}$ (10)
 > $\mathrm{P3}≔{x}^{2}-\mathrm{RootOf}\left({x}^{2}-x\right)$
 ${\mathrm{P3}}{≔}{{x}}^{{2}}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}\right)$ (11)
 > $\mathrm{Q3}≔{x}^{2}-2x+1$
 ${\mathrm{Q3}}{≔}{{x}}^{{2}}{-}{2}{}{x}{+}{1}$ (12)
 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P3},\mathrm{Q3}\right)\right)$
 evala/Gcd/preproc0: a case discussion result: Array(1..2, {1 = [[1], [RootOf(_Z^2-_Z) = 0]], 2 = [[x-1], [RootOf(_Z^2-_Z) = 1]]}) MergeGcds: Merge result: #cases: 2; gcd(s): [[1, [0]], [x-1, [1]]]

To pretend that all the defining polynomials are irreducible, use the option 'independent':

 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P3},\mathrm{Q3}\right),'\mathrm{independent}'\right)$
 ${1}$ (13)

Alternatively, use indexed RootOfs:

 > $\mathrm{P31}≔{x}^{2}-\mathrm{RootOf}\left({x}^{2}-x,\mathrm{index}=1\right)$
 ${\mathrm{P31}}{≔}{{x}}^{{2}}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{,}{\mathrm{index}}{=}{1}\right)$ (14)
 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P31},\mathrm{Q3}\right)\right)$
 ${1}$ (15)
 > $\mathrm{P32}≔{x}^{2}-\mathrm{RootOf}\left({x}^{2}-x,\mathrm{index}=2\right)$
 ${\mathrm{P32}}{≔}{{x}}^{{2}}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}{,}{\mathrm{index}}{=}{2}\right)$ (16)
 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P32},\mathrm{Q3}\right)\right)$
 ${x}{-}{1}$ (17)
 > $\mathrm{Q4}≔{x}^{2}+x$
 ${\mathrm{Q4}}{≔}{{x}}^{{2}}{+}{x}$ (18)
 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P3},\mathrm{Q4}\right)\right)$
 evala/Gcd/preproc0: a case discussion result: Array(1..2, {1 = [[x], [RootOf(_Z^2-_Z) = 0]], 2 = [[x+1], [RootOf(_Z^2-_Z) = 1]]}) MergeGcds: Merge result: #cases: 1; gcd(s): [[x+RootOf(_Z^2-_Z), [RootOf(_Z^2-_Z)]]]
 ${x}{+}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{\mathrm{_Z}}\right)$ (19)
 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P3},\mathrm{Q4}\right),'\mathrm{independent}'\right)$
 ${1}$ (20)
 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P31},\mathrm{Q4}\right)\right)$
 ${x}$ (21)
 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P32},\mathrm{Q4}\right)\right)$
 ${x}{+}{1}$ (22)

A bivariate example with dependent RootOfs:

 > $\mathrm{alias}\left(s=\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right),t=\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-\mathrm{_Z}+\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\right)-2\right)\right):$
 > $\mathrm{P5}≔\left(t-s\right)\left(y+1\right)x\cdot 3+\left(s+t-1\right){y}^{2}x\cdot 4$
 ${\mathrm{P5}}{≔}{3}{}\left({t}{-}{s}\right){}\left({y}{+}{1}\right){}{x}{+}{4}{}\left({s}{+}{t}{-}{1}\right){}{{y}}^{{2}}{}{x}$ (23)
 > $\mathrm{Q5}≔\left(t-s\right)\left(y+1\right)x\cdot 6+\left(s+t-1\right)y{\left(y-1\right)}^{2}x\cdot 8$
 ${\mathrm{Q5}}{≔}{6}{}\left({t}{-}{s}\right){}\left({y}{+}{1}\right){}{x}{+}{8}{}\left({s}{+}{t}{-}{1}\right){}{y}{}{\left({y}{-}{1}\right)}^{{2}}{}{x}$ (24)
 > $\mathrm{evala}\left(\mathrm{Gcd}\left(\mathrm{P5},\mathrm{Q5}\right)\right)$
 evala/Gcd/preproc0: a case discussion result: Array(1..2, {1 = [[(y+1)*x], [RootOf(_Z^2-_Z+RootOf(_Z^2-2)-2) = -RootOf(_Z^2-2)+1]], 2 = [[y*x], [RootOf(_Z^2-_Z+RootOf(_Z^2-2)-2) = RootOf(_Z^2-2)]]}) MergeGcds: Merge result: #cases: 1; gcd(s): [[y*x+(1/7*(-2*s-1)*t+1/7*s+4/7)*x, [s, t]]]
 ${y}{}{x}{+}\left(\frac{{1}}{{7}}{}\left({-}{2}{}{s}{-}{1}\right){}{t}{+}\frac{{1}}{{7}}{}{s}{+}\frac{{4}}{{7}}\right){}{x}$ (25)
 >