53.7 Gcd and Lcm

In the first two forms Gcd returns the greatest common divisor of the ring elements r1, r2, ... resp. of the ring elements in the list list in the ring R. In the second two forms Gcd returns the greatest common divisor of the ring elements r1, r2, ... resp. of the ring elements in the list list in their default ring (see DefaultRing). R must be a Euclidean ring (see IsEuclideanRing) so that QuotientRemainder (see QuotientRemainder) can be applied to its elements. Gcd returns the standard associate (see StandardAssociate) of the greatest common divisors.

A greatest common divisor of the elements r₁, r₂... etc. of the ring R is an element of largest Euclidean degree (see EuclideanDegree) that is a divisor of r₁, r₂... etc. We define gcd( r, 0_R ) = gcd( 0_R, r ) = StandardAssociate( r ) and gcd( 0_R, 0_R ) = 0_R.

gap> Gcd( Integers, [ 10, 15 ] );
5

GcdOp is the operation to compute the greatest common divisor of two ring elements r, s in the ring R or in their default ring.

In the first two forms GcdRepresentation returns the representation of the greatest common divisor of the ring elements r1, r2, ... resp. of the ring elements in the list list in the ring R. In the second two forms GcdRepresentation returns the representation of the greatest common divisor of the ring elements r1, r2, ... resp. of the ring elements in the list list in their default ring (see DefaultRing). R must be a Euclidean ring (see IsEuclideanRing) so that Gcd (see Gcd) can be applied to its elements.

The representation of the gcd g of the elements r₁, r₂... etc. of a ring R is a list of ring elements s₁, s₂... etc. of R, such that g = s₁ r₁ + s₂ r₂ .... That this representation exists can be shown using the Euclidean algorithm, which in fact can compute those coefficients.

gap> x:= Indeterminate( Rationals, "x" );;      
gap> GcdRepresentation( x^2+1, x^3+1 );   
[ 1/2-1/2*x-1/2*x^2, 1/2+1/2*x ]

GcdRepresentationOp is the operation to compute the representation of the greatest common divisor of two ring elements r, s in the ring R or in their default ring, respectively.

In the first two forms Lcm returns the least common multiple of the ring elements r1, r2, ... resp. of the ring elements in the list list in the ring R. In the second two forms Lcm returns the least common multiple of the ring elements r1, r2, ... resp. of the ring elements in the list list in their default ring (see DefaultRing).

R must be a Euclidean ring (see IsEuclideanRing) so that Gcd (see Gcd) can be applied to its elements. Lcm returns the standard associate (see StandardAssociate) of the least common multiples.

A least common multiple of the elements r₁, r₂... etc. of the ring R is an element of smallest Euclidean degree (see EuclideanDegree) that is a multiple of r₁, r₂... etc. We define lcm( r, 0_R ) = lcm( 0_R, r ) = StandardAssociate( r ) and Lcm( 0_R, 0_R ) = 0_R.

Lcm uses the equality lcm(m,n) = m\*n / gcd(m,n) (see Gcd).

LcmOp is the operation to compute the least common multiple of two ring elements r, s in the ring R or in their default ring, respectively.

In the first form QuotientMod returns the quotient of the ring elements r and s modulo the ring element m in the ring R. In the second form QuotientMod returns the quotient of the ring elements r and s modulo the ring element m in their default ring (see DefaultRing). R must be a Euclidean ring (see IsEuclideanRing) so that EuclideanRemainder (see EuclideanRemainder) can be applied. If the modular quotient does not exist, fail is returned.

The quotient q of r and s modulo m is an element of R such that q s = r modulo m, i.e., such that q s - r is divisible by m in R and that q is either 0 (if r is divisible by m) or the Euclidean degree of q is strictly smaller than the Euclidean degree of m.

gap> QuotientMod( 7, 2, 3 );
2

In the first form PowerMod returns the e-th power of the ring element r modulo the ring element m in the ring R. In the second form PowerMod returns the e-th power of the ring element r modulo the ring element m in their default ring (see DefaultRing). e must be an integer. R must be a Euclidean ring (see IsEuclideanRing) so that EuclideanRemainder (see EuclideanRemainder) can be applied to its elements.

If e is positive the result is r^e modulo m. If e is negative then PowerMod first tries to find the inverse of r modulo m, i.e., i such that i r = 1 modulo m. If the inverse does not exist an error is signalled. If the inverse does exist PowerMod returns PowerMod( R, i, -e, m ).

PowerMod reduces the intermediate values modulo m, improving performance drastically when e is large and m small.

gap> PowerMod( 12, 100000, 7 );
2

InterpolatedPolynomial returns, for given lists x, y of elements in a ring R of the same length n, say, the unique polynomial of degree less than n which has value y[i] at x[i], for all i = 1,...,n. Note that the elements in x must be distinct.

gap>  InterpolatedPolynomial( Integers, [ 1, 2, 3 ], [ 5, 7, 0 ] );
-6+31/2*x-9/2*x^2

[Top] [Previous] [Up] [Index]