#5660 gcd with tellrat extensions depends on variable names and argument order

[David Scherfgen]

By Claude:

With algebraic: true, gcd gives wrong results or signals errors for polynomials over tellrat extensions, depending on the names of the variables and on the order of the arguments. With one extension, renaming a variable changes the result:

(%i1) display2d: false$
(%i2) algebraic: true$
(%i3) tellrat(r^2-2)$
(%i4) gcd(expand(r*(r+a+1)), r+a+1);
(%o4) 1
(%i5) gcd(expand(r*(r+a+1)), r+a+1, r, a);
(%o5) r+a+1
(%i6) gcd(expand(r*(r+x+1)), r+x+1);
(%o6) x+r+1

r+a+1 divides both arguments, so (%o4) should be r+a+1. Listing the variables with the generator first, as in (%i5), gives the right result, and so does renaming a to x.

With two extensions, a variable that occurs only in the second argument makes gcd return the second argument, which does not divide the first. Swapping the arguments gives the right result:

(%i1) display2d: false$
(%i2) algebraic: true$
(%i3) tellrat(a^2-2, b^2-3)$
(%i4) f: (a*b+1)*x$
(%i5) g: expand((1-a*y)*(a*b+1)*x)$
(%i6) gcd(f, g);
(%o6) x*(-a*y+b*(a-2*y)+1)
(%i7) gcd(g, f);
(%o7) (a*b+1)*x

With an extension of an extension, and with an extension of a finite field, similar input signals errors, while swapping the arguments gives the right results x+1 and z+1:

(%i1) display2d: false$
(%i2) algebraic: true$
(%i3) tellrat(a^2-2, b^2-a)$
(%i4) gcd(a*(x+1), (a*b+3)*(x+1));
CQUOTIENT: quotient is not exact
 -- an error. To debug this try: debugmode(true);
(%i5) gcd((a*b+3)*(x+1), a*(x+1));
(%o5) x+1

(%i1) display2d: false$
(%i2) algebraic: true$
(%i3) modulus: 2$
(%i4) tellrat(a^2+a+1)$
(%i5) gcd(a*y*(z+1), (a*u*y+y+a)*(z+1));
PQUOTIENT: Quotient by a polynomial of higher degree (case 2b)
 -- an error. To debug this try: debugmode(true);
(%i6) gcd((a*u*y+y+a)*(z+1), a*y*(z+1));
(%o6) z+1

The gcd of two polynomials should not depend on the names of their variables or on the order of the arguments.