10.14 Ring Functions for Integers

As was already noted in the introduction to this chapter the integers form a Euclidean ring, so all ring functions (see chapter Rings) are applicable to the integers. This section comments on the implementation of those functions for the integers and tells you how you can call the corresponding functions directly, for example to save time.

IsPrime( Integers, n )

This is implemented by IsPrimeInt, which you can call directly to save a little bit of time (see IsPrimeInt).

Factors( Integers, n )

This is implemented as by FactorsInt, which you can call directly to save a little bit of time (see FactorsInt).

EuclideanDegree( Integers, n )

The Euclidean degree of an integer is of course simply the absolute value of the integer. Calling AbsInt directly will be a little bit faster.

EuclideanRemainder( Integers, n, m )

This is implemented as RemInt( n, m ), which you can use directly to save a lot of time.

EuclideanQuotient( Integers, n, m )

This is implemented as QuoInt( n, m ), which you can use directly to save a lot of time.

QuotientRemainder( Integers, n, m )

This is implemented as [ QuoInt(n,m), RemInt(n,m) ], which you can use directly to save a lot of time.

QuotientMod( Integers, n1, n2, m )

This is implemented as (n1 / n2) mod m, which you can use directly to save a lot of time.

PowerMod( Integers, n, e, m )

This is implemented by PowerModInt, which you can call directly to save a little bit of time. Note that using n ^ e mod m will generally be slower, because it can not reduce intermediate results like PowerMod.

Gcd( Integers, n1, n2.. )

This is implemented by GcdInt, which you can call directly to save a lot of time. Note that GcdInt takes only two arguments, not several as Gcd does.

Gcdex( n1, n2 )

Gcdex returns a record. The component gcd is the gcd of n1 and n2.

The components coeff1 and coeff2 are integer cofactors such that
g.gcd = g.coeff1*n1 + g.coeff2*n2.
If n1 and n2 both are nonzero, AbsInt( g.coeff1 ) is less than or equal to AbsInt(n2) / (2*g.gcd) and AbsInt( g.coeff2 ) is less than or equal to AbsInt(n1) / (2*g.gcd).

The components coeff3 and coeff4 are integer cofactors such that
0 = g.coeff3*n1 + g.coeff4*n2.
If n1 or n2 or are both nonzero coeff3 is -n2 / g.gcd and coeff4 is n1 / g.gcd.

The coefficients always form a unimodular matrix, i.e., the determinant
g.coeff1*g.coeff4 - g.coeff3*g.coeff2
is 1 or -1.

    gap> Gcdex( 123, 66 );
    rec(
      gcd := 3,
      coeff1 := 7,
      coeff2 := -13,
      coeff3 := -22,
      coeff4 := 41 )
          # 3 = 7\*123 - 13\*66, 0 = -22\*123 + 41\*66
    gap> Gcdex( 0, -3 );
    rec(
      gcd := 3,
      coeff1 := 0,
      coeff2 := -1,
      coeff3 := 1,
      coeff4 := 0 )
    gap> Gcdex( 0, 0 );
    rec(
      gcd := 0,
      coeff1 := 1,
      coeff2 := 0,
      coeff3 := 0,
      coeff4 := 1 ) 

Lcm( Integers, n1, n2.. )

This is implemented as LcmInt, which you can call directly to save a little bit of time. Note that LcmInt takes only two arguments, not several as Lcm does.

Previous Up Top Next
Index