# [Maxima] gcd strangeness

Richard Fateman fateman at cs.berkeley.edu
Mon Mar 13 23:12:43 CST 2006

```subres is no longer new.  It is about 40 years old.
the choice of which gcd algorithm to use for polynomials
depends on the kinds of inputs and the expected output.
For example, if you expect the gcd to be large,
subres is good.

spmod is probably the best speed.

gcd is probably not defined mathematically unless you
describe the domain, though the answers given by
the gcd program look pretty random.

RJF

----- Original Message -----
From: "Robert Dodier" <robert.dodier at gmail.com>
To: "Maxima" <maxima at math.utexas.edu>
Sent: Monday, March 13, 2006 8:45 PM
Subject: [Maxima] gcd strangeness

> Hello,
>
> One of the simplifications of mod(x, y) first computes gcd(x, y).
> However gcd yields some results I didn't expect.
> e.g.   gcd (x, y/2); => 1/2,   gcd (x, y/a); => 1/a,   gcd (x - 1/2, %e);
> => 1/2
> I expected 1 in these cases. What is the interpretation of gcd
> in which these make sense? Thanks for any insights.
>
> Robert Dodier
>
> PS. If anyone has some remarks which clarify this description of gcd,
> I will update the texinfo file. In particular, what are the various
> algorithms,
> and why would one be chosen over another.
>
> -- Function: gcd (<p_1>, <p_2>, <x_1>, ...)
>     Returns the greatest common divisor of <p_1> and <p_2>.  The flag
>     `gcd' determines which algorithm is employed.  Setting `gcd' to
>     `ez', `eez', `subres', `red', or `spmod' selects the `ezgcd', New
>     `eez' `gcd', subresultant `prs', reduced, or modular algorithm,
>     respectively.  If `gcd' `false' then GCD(p1,p2,var) will always
>     return 1 for all var.  Many functions (e.g.  `ratsimp', `factor',
>     etc.) cause gcd's to be taken implicitly.  For homogeneous
>     polynomials it is recommended that `gcd' equal to `subres' be
>     used.  To take the gcd when an algebraic is present, e.g.
>     GCD(X^2-2*SQRT(2)*X+2,X-SQRT(2)); , `algebraic' must be `true' and
>     `gcd' must not be `ez'.  `subres' is a new algorithm, and people
>     who have been using the `red' setting should probably change it to
>     `subres'.
>
>     The `gcd' flag, default: `subres', if `false' will also prevent
>     the greatest common divisor from being taken when expressions are
>     converted to canonical rational expression (CRE) form.  This will
>     sometimes speed the calculation if gcds are not required.
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>

```