# 19.18 Ring Functions for Polynomial Rings

As was already noted in the introduction to this chapter polynomial rings are rings, so all ring functions (see chapter Rings) are applicable to polynomial rings. This section comments on the implementation of those functions.

Let R be a commutative ring-with-one or a field and let P be the polynomial ring over R.

EuclideanDegree( P, f )

P is an Euclidean ring if and only if R is field. In this case the Euclidean degree of f is simply the degree of f. If R is not a field then the function signals an error.

gap> x := Indeterminate(Rationals);; x.name := "x";;
gap> EuclideanDegree( x^10 + x^2 + 1 );
10
gap> EuclideanDegree( x^0 );
0

EuclideanRemainder( P, f, g )

P is an Euclidean ring if and only if R is field. In this case it is possible to divide f by g with remainder.

gap> x := Indeterminate(Rationals);; x.name := "x";;
gap> EuclideanRemainder( (x+1)*(x+2)+5, x+1 );
5*x^0

EuclideanQuotient( P, f, g )

P is an Euclidean ring if and only if R is field. In this case it is possible to divide f by g with remainder.

gap> x := Indeterminate(Rationals);; x.name := "x";;
gap> EuclideanQuotient( (x+1)*(x+2)+5, x+1 );
x + 2

QuotientRemainder( P, f, g )

P is an Euclidean ring if and only if R is field. In this case it is possible to divide f by g with remainder.

gap> x := Indeterminate(Rationals);; x.name := "x";;
gap> QuotientRemainder( (x+1)*(x+2)+5, x+1 );
[ x + 2, 5*x^0 ]

Gcd( P, f, g )

P is an Euclidean ring if and only if R is field. In this case you can compute the greatest common divisor of f and g using Gcd.

gap> x := Indeterminate(Rationals);; x.name := "x";;
gap> g := x^2 + 2*x + 1;;
gap> h := x^2 - 1;;
gap> Gcd( g, h );
x + 1
gap> GcdRepresentation( g, h );
[ 1/2*x^0, -1/2*x^0 ]
gap> g * (1/2) * x^0 - h * (1/2) * x^0;
x + 1

Factors( P, f )

This method is implemented for polynomial rings P over a domain R, where R is either a finite field, the rational numbers, or an algebraic extension of either one. If char R is a prime, f is factored using a Cantor-Zassenhaus algorithm.

gap> f5 := GF(5);; f5.name := "f5";;
gap> x  := Indeterminate(f5);; x.name := "x";;
gap> g := x^20 + x^8 + 1;
Z(5)^0*(x^20 + x^8 + 1)
gap> Factors(g);
[ Z(5)^0*(x^8 + 4*x^4 + 2), Z(5)^0*(x^12 + x^8 + 4*x^4 + 3) ]

If char R is 0, a quadratic Hensel lift is used.

gap> x := Indeterminate(Rationals);; x.name := "x";;
gap> f:=x^105-1;
x^105 - 1
gap> Factors(f);
[ x - 1, x^2 + x + 1, x^4 + x^3 + x^2 + x + 1,
x^6 + x^5 + x^4 + x^3 + x^2 + x + 1,
x^8 - x^7 + x^5 - x^4 + x^3 - x + 1,
x^12 - x^11 + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1,
x^24 - x^23 + x^19 - x^18 + x^17 - x^16 + x^14 - x^13 + x^12 - x^
11 + x^10 - x^8 + x^7 - x^6 + x^5 - x + 1,
x^48 + x^47 + x^46 - x^43 - x^42 - 2*x^41 - x^40 - x^39 + x^36 + x^
35 + x^34 + x^33 + x^32 + x^31 - x^28 - x^26 - x^24 - x^22 - x^
20 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 - x^9 - x^8 - 2*x^
7 - x^6 - x^5 + x^2 + x + 1 ]

As f is an element of P if and only if the base ring of f is R you must embed the polynomial into the polynomial ring P if it is written as polynomial over a subring.

gap> f25 := GF(25);; Indeterminate(f25).name := "y";;
gap> l := Factors( EmbeddedPolynomial( PolynomialRing(f25), g ) );
[ y^4 + Z(5^2)^13, y^4 + Z(5^2)^17, y^6 + Z(5)^3*y^2 + Z(5^2)^3,
y^6 + Z(5)^3*y^2 + Z(5^2)^15 ]
gap> l[1] * l[2];
y^8 + Z(5)^2*y^4 + Z(5)
gap> l[3] * l[4];
y^12 + y^8 + Z(5)^2*y^4 + Z(5)^3

StandardAssociate( P, f )

For a ring R the standard associate a of f is a multiple of f such that the leading coefficient of a is the standard associate in R. For a field R the standard associate a of f is a multiple of f such that the leading coefficient of a is 1.

gap> x := Indeterminate(Integers);; x.name := "x";;
gap> StandardAssociate( -2 * x^3 - x );
2*x^3 + x

GAP 3.4.4
April 1997