GAP Manual: 5.27. GcdRepresentation

GcdRepresentation( r1, r2... )
GcdRepresentation( R, r1, r2... )

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

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

    gap> GcdRepresentation( 123, 66 );
    [ 7, -13 ]    # 3 = 7\*123 - 13\*66
    gap> Gcd( 123, 66 ) = last * [ 123, 66 ];
    true 

GcdRepresentation calls R.operations.GcdRepresentation repeatedly, each time passing the gcd result of the previous call and the next argument, and returns the value of the last call.

The default function called this way is RingOps.GcdRepresentation, which applies the Euclidean algorithm to compute the greatest common divisor and its representation. Special categories of rings overlay this default function with more efficient functions.