Rings are important algebraic domains. Mathematically a ring is a set
R with two operations +
and *
called addition and multiplication.
(R,+) must be an abelian group. The identity of this group is called
0R. (R-{0R},*) must be a monoid. If this monoid has an
identity element it is called 1R.
Important examples of rings are the integers (see Integers), the Gaussian integers (see Gaussians), the integers of a cyclotomic field (see Subfields of Cyclotomic Fields), and matrices (see Matrices).
This chapter contains sections that describe how to test whether a domain is a ring (see IsRing), and how to find the smallest and the default ring in which a list of elements lies (see Ring and DefaultRing).
The next sections describe the operations applicable to ring elements (see Comparisons of Ring Elements, Operations for Ring Elements, Quotient).
The next sections describe the functions that test whether a ring has certain properties (IsCommutativeRing, IsIntegralRing, IsUniqueFactorizationRing, and IsEuclideanRing).
The next sections describe functions that are related to the units of a ring (see IsUnit, Units, IsAssociated, StandardAssociate, and Associates).
Then come the sections that describe the functions that deal with the irreducible and prime elements of a ring (see IsIrreducible, IsPrime, and Factors).
Then come the sections that describe the functions that are applicable to elements of rings (see EuclideanDegree, EuclideanRemainder, EuclideanQuotient, QuotientRemainder, QuotientMod, PowerMod, Gcd, GcdRepresentation, Lcm).
The last section describes how ring records are represented internally (see Ring Records).
Because rings are a category of domains all functions applicable to domains are also applicable to rings (see chapter Domains) .
All functions described in this chapter are in LIBNAME/"ring.g"
.
IsRing( domain )
IsRing
returns true
if the object domain is a ring record,
representing a ring (see Ring Records), and false
otherwise.
More precisely IsRing
tests whether domain is a ring record (see
Ring Records). So for example a matrix group may in fact be a ring,
yet IsRing
would return false
.
gap> IsRing( Integers ); true gap> IsRing( Rationals ); false #Rationals
is a field record not a ring record gap> IsRing( rec( isDomain := true, isRing := true ) ); true # it is possible to foolIsRing
Ring( r, s... )
Ring( list )
In the first form Ring
returns the smallest ring that contains all the
elements r, s... etc. In the second form Ring
returns the smallest
ring that contains all the elements in the list list. If any element
is not an element of a ring or if the elements lie in no common ring an
error is raised.
gap> Ring( 1, -1 ); Integers gap> Ring( [10..20] ); Integers
Ring
differs from DefaultRing
(see DefaultRing) in that it returns
the smallest ring in which the elements lie, while DefaultRing
may
return a larger ring if that makes sense.
DefaultRing( r, s... )
DefaultRing( list )
In the first form DefaultRing
returns the default ring that contains
all the elements r, s... etc. In the second form DefaultRing
returns the default ring that contains all the elements in the list
list. If any element is not an element of a ring or if the elements
lie in no common ring an error is raised.
The ring returned by DefaultRing
need not be the smallest ring in which
the elements lie. For example for elements from cyclotomic fields
DefaultRing
may return the ring of integers of the smallest cyclotomic
field in which the elements lie, which need not be the smallest ring
overall, because the elements may in fact lie in a smaller number field
which is not a cyclotomic field.
For the exact definition of the default ring of a certain type of elements read the chapter describing this type.
DefaultRing
is used by the ring functions like Quotient
, IsPrime
,
Factors
, or Gcd
if no explicit ring is given.
gap> DefaultRing( 1, -1 ); Integers gap> DefaultRing( [10..20] ); Integers
Ring
(see Ring) differs from DefaultRing
in that it returns the
smallest ring in which the elements lie, while DefaultRing
may return a
larger ring if that makes sense.
5.4 Comparisons of Ring Elements
r = s
r <> s
The equality operator =
evaluates to true
if the two ring elements
r and s are equal, and to false
otherwise. The inequality operator
<>
evaluates to true
if the two ring elements r and s are not
equal, and to false
otherwise. Note that any two ring elements can be
compared, even if they do not lie in compatible rings. In this case they
can, of course, never be equal. For each type of rings the equality of
those ring elements is given in the respective chapter.
Ring elements can also be compared with objects of other types. Of course they are never equal.
r < s
r <= s
r > s
r >= s
The operators <
, <=
, >
, and >=
evaluate to true
if the ring
element r is less than, less than or equal to, greater than, or greater
than or equal to the ring element s, and to false
otherwise. For
each type of rings the definition of the ordering of those ring elements
is given in the respective chapter. The ordering of ring elements is as
follows. Rationals are smallest, next are cyclotomics, followed by
finite ring elements.
Ring elements can also be compared with objects of other types. They are smaller than everything else.
5.5 Operations for Ring Elements
The following operations are always available for ring elements. Of course the operands must lie in compatible rings, i.e., the rings must be equal, or at least have a common superring.
r + s
The operator +
evaluates to the sum of the two ring elements r and
s, which must lie in compatible rings.
r - s
The operator -
evaluates to the difference of the two ring elements
r and s, which must lie in compatible rings.
r * s
The operator *
evaluates to the product of the two ring elements r
and s, which must lie in compatible rings.
r ^ n
The operator ^
evaluates to the n-th power of the ring element r.
If n is a positive integer then r^n
is r*r*..*r
(n factors). If n is a negative integer r^n
is defined as
1 / r-n. If 0 is raised to a negative power an error is
signalled. Any ring element, even 0, raised to the 0-th power yields 1.
For the precedence of the operators see Operations.
Note that the quotient operator /
usually performs the division in the
quotient field of the ring. To compute a quotient in a ring use the
function Quotient
(see Quotient).
Quotient( r, s )
Quotient( R, r, s )
In the first form Quotient
returns the quotient of the two ring
elements r and s in their default ring (see DefaultRing). In the
second form Quotient
returns the quotient of the two ring elements r
and s in the ring R. It returns false
if the quotient does not
exist.
gap> Quotient( 4, 2 ); 2 gap> Quotient( Integers, 3, 2 ); false
Quotient
calls R.operations.Quotient( R, r, s )
and returns
the value.
The default function called this way is RingOps.Quotient
, which just
signals an error, because there is no generic method to compute the
quotient of two ring elements. Thus special categories of rings must
overlay this default function with other functions.
IsCommutativeRing( R )
IsCommutativeRing
returns true
if the ring R is commutative and
false
otherwise.
A ring R is called commutative if for all elements r and s of R we have r s = s r.
gap> IsCommutativeRing( Integers ); true
IsCommutativeRing
first tests whether the flag R.isCommutativeRing
is bound. If the flag is bound, it returns this value. Otherwise it
calls R.operations.IsCommutativeRing( R )
, remembers the returned
value in R.isCommutativeRing
, and returns it.
The default function called this way is RingOps.IsCommutativeRing
,
which tests whether all the generators commute if the component
R.generators
is bound, and tests whether all elements commute
otherwise, unless R is infinite. This function is seldom overlaid,
because most rings already have the flag bound.
IsIntegralRing( R )
IsIntegeralRing
returns true
if the ring R is integral and false
otherwise.
A ring R is called integral if it is commutative and if for all elements r and s of R we have r s = 0R implies that either r or s is 0R.
gap> IsIntegralRing( Integers ); true
IsIntegralRing
first tests whether the flag R.isIntegralRing
is
bound. If the flag is bound, it returns this value. Otherwise it calls
R.operations.IsIntegralRing( R )
, remembers the returned value in
R.isIntegralRing
, and returns it.
The default function called this way is RingOps.IsIntegralRing
, which
tests whether the product of each pair of nonzero elements is unequal to
zero, unless R is infinite. This function is seldom overlaid, because
most rings already have the flag bound.
IsUniqueFactorizationRing( R )
IsUniqueFactorizationRing
returns true
if R is a unique
factorization ring and false
otherwise.
A ring R is called a unique factorization ring if it is an integral ring, and every element has a unique factorization into irreducible elements, i.e., a unique representation as product of irreducibles (see IsIrreducible). Unique in this context means unique up to permutations of the factors and up to multiplication of the factors by units (see Units).
gap> IsUniqueFactorizationRing( Integers ); true
IsUniqueFactorizationRing
tests whether R.isUniqueFactorizationRing
is bound. If the flag is bound, it returns this value. If this flag has
no assigned value it calls the function
R.operations.IsUniqueFactorizationRing( R )
, remembers the returned
value in R.isUniqueFactorizationRing
, and returns it.
The default function called this way is
RingOps.IsUniqueFactorizationRing
, which just signals an error, since
there is no generic method to test whether a ring is a unique
factorization ring. Special categories of rings thus must either have
the flag bound or overlay this default function.
IsEuclideanRing( R )
IsEuclideanRing
returns true
if the ring R is a Euclidean ring and
false
otherwise.
A ring R is called a Euclidean ring if it is an integral ring and there exists a function δ, called the Euclidean degree, from R-{0R} to the nonnegative integers, such that for every pair r ∈ R and s ∈ R-{0R} there exists an element q such that either r - q s = 0R or δ(r - q s) < δ( s ). The existence of this division with remainder implies that the Euclidean algorithm can be applied to compute a greatest common divisor of two elements, which in turn implies that R is a unique factorization ring.
gap> IsEuclideanRing( Integers ); true
IsEuclideanRing
first tests whether the flag R.isEuclideanRing
is
bound. If the flag is bound, it returns this value. Otherwise it calls
R.operations.IsEuclideanRing( R )
, remembers the returned value in
R.isEuclideanRing
, and returns it.
The default function called this way is RingOps.IsEuclideanRing
, which
just signals an error, because there is no generic way to test whether a
ring is a Euclidean ring. This function is seldom overlaid because most
rings already have the flag bound.
IsUnit( r )
IsUnit( R, r )
In the first form IsUnit
returns true
if the ring element r is a
unit in its default ring (see DefaultRing). In the second form
IsUnit
returns true
if r is a unit in the ring R.
An element r is called a unit in a ring R, if r has an inverse in R.
gap> IsUnit( Integers, 2 ); false gap> IsUnit( Integers, -1 ); true
IsUnit
calls R.operations.IsUnit( R, r )
and returns the value.
The default function called this way is RingOps.IsUnit
, which tries to
compute the inverse of r with R.operations.Quotient( R, R.one,
r )
and returns true
if the result is not false
, and false
otherwise. Special categories of rings overlay this default function
with more efficient functions.
Units( R )
Units
returns the group of units of the ring R. This may either be
returned as a list or as a group described by a group record (see
Groups).
An element r is called a unit of a ring R, if r has an inverse in R. It is easy to see that the set of units forms a multiplicative group.
gap> Units( Integers ); [ -1, 1 ]
Units
first tests whether the component R.units
is bound. If the
component is bound, it returns this value. Otherwise it calls
R.operations.Units( R )
, remembers the returned value in
R.units
, and returns it.
The default function called this way is RingOps.Units
, which runs over
all elements of R and tests for each whether it is a unit, provided
that R is finite. Special categories of rings overlay this default
function with more efficient functions.
IsAssociated( r, s )
IsAssociated( R, r, s )
In the first form IsAssociated
returns true
if the two ring elements
r and s are associated in their default ring (see DefaultRing) and
false
otherwise. In the second form IsAssociated
returns true
if
the two ring elements r and s are associated in the ring R and
false
otherwise.
Two elements r and s of a ring R are called associates if there is a unit u of R such that r u = s.
gap> IsAssociated( Integers, 2, 3 ); false gap> IsAssociated( Integers, 17, -17 ); true
IsAssociated
calls R.operations.IsAssociated( R, r, s )
and
returns the value.
The default function called this way is RingOps.IsAssociated
, which
tries to compute the quotient of r and s and returns true
if the
quotient exists and is a unit. Special categories of rings overlay this
default function with more efficient functions.
StandardAssociate( r )
StandardAssociate( R, r )
In the first form StandardAssociate
returns the standard associate of
the ring element r in its default ring (see DefaultRing). In the
second form StandardAssociate
returns the standard associate of the
ring element r in the ring R.
The standard associate of an ring element r of R is an associated element of r which is, in a ring dependent way, distinguished among the set of associates of r. For example, in the ring of integers the standard associate is the absolute value.
gap> StandardAssociate( Integers, -17 ); 17
StandardAssociate
calls R.operations.StandardAssociate( R, r )
and returns the value.
The default function called this way is RingOps.StandardAssociate
,
which just signals an error, because there is no generic way even to
define the standard associate. Thus special categories of rings must
overlay this default function with other functions.
Associates( r )
Associates( R, r )
In the first form Associates
returns the set of associates of the ring
element r in its default ring (see DefaultRing). In the second form
Associates
returns the set of associates of r in the ring R.
Two elements r and s of a ring R are called associate if there is a unit u of R such that r u = s.
gap> Associates( Integers, 17 ); [ -17, 17 ]
Associates
calls R.operations.Associates( R, r )
and returns
the value.
The default function called this way is RingOps.Associates
, which
multiplies the set of units of R with the element r, and returns the
set of those elements. Special categories of rings overlay this default
function with more efficient functions.
IsIrreducible( r )
IsIrreducible( R, r )
In the first form IsIrreducible
returns true
if the ring element r
is irreducible in its default ring (see DefaultRing) and false
otherwise. In the second form IsIrreducible
returns true
if the ring
element r is irreducible in the ring R and false
otherwise.
An element r of a ring R is called irreducible if there is no nontrivial factorization of r in R, i.e., if there is no representation of r as product s t such that neither s nor t is a unit (see IsUnit). Each prime element (see IsPrime) is irreducible.
gap> IsIrreducible( Integers, 4 ); false gap> IsIrreducible( Integers, 3 ); true
IsIrreducible
calls R.operations.IsIrreducible( R, r )
and
returns the value.
The default function called this way is RingOps.IsIrreducible
, which
justs signals an error, because there is no generic way to test whether
an element is irreducible. Thus special categories of rings must overlay
this default function with other functions.
IsPrime( r )
IsPrime( R, r )
In the first form IsPrime
returns true
if the ring element r is a
prime in its default ring (see DefaultRing) and false
otherwise. In
the second form IsPrime
returns true
if the ring element r is a
prime in the ring R and false
otherwise.
An element r of a ring R is called prime if for each pair s and t such that r divides s t the element r divides either s or t. Note that there are rings where not every irreducible element (see IsIrreducible) is a prime.
gap> IsPrime( Integers, 4 ); false gap> IsPrime( Integers, 3 ); true
IsPrime
calls R.operations.IsPrime( R, r )
and returns the
value.
The default function called this way is RingOps.IsPrime
, which just
signals an error, because there is no generic way to test whether an
element is prime. Thus special categories of rings must overlay this
default function with other functions.
Factors( r )
Factors( R, r )
In the first form Factors
returns the factorization of the ring element
r in its default ring (see DefaultRing). In the second form
Factors
returns the factorization of the ring element r in the ring
R. The factorization is returned as a list of primes (see IsPrime).
Each element in the list is a standard associate (see
StandardAssociate) except the first one, which is multiplied by a unit
as necessary to have Product( Factors( R, r ) ) = r
. This list
is usually also sorted, thus smallest prime factors come first. If r
is a unit or zero, Factors( R, r ) = [ r ]
.
gap> Factors( -Factorial(6) ); [ -2, 2, 2, 2, 3, 3, 5 ] gap> Set( Factors( Factorial(13)/11 ) ); [ 2, 3, 5, 7, 13 ] gap> Factors( 2^63 - 1 ); [ 7, 7, 73, 127, 337, 92737, 649657 ] gap> Factors( 10^42 + 1 ); [ 29, 101, 281, 9901, 226549, 121499449, 4458192223320340849 ]
Factors
calls R.operations.Factors( R, r )
and returns the
value.
The default function called this way is RingOps.Factors
, which just
signals an error, because there is no generic way to compute the
factorization of ring elements. Thus special categories of ring elements
must overlay this default function with other functions.
EuclideanDegree( r )
EuclideanDegree( R, r )
In the first form EuclideanDegree
returns the Euclidean degree of the
ring element r in its default ring. In the second form
EuclideanDegree
returns the Euclidean degree of the ring element in the
ring R. R must of course be an Euclidean ring (see
IsEuclideanRing).
A ring R is called a Euclidean ring, if it is an integral ring, and there exists a function δ, called the Euclidean degree, from R-{0R} to the nonnegative integers, such that for every pair r ∈ R and s ∈ R-{0R} there exists an element q such that either r - q s = 0R or δ(r - q s) < δ( s ). The existence of this division with remainder implies that the Euclidean algorithm can be applied to compute a greatest common divisors of two elements, which in turn implies that R is a unique factorization ring.
gap> EuclideanDegree( Integers, 17 ); 17 gap> EuclideanDegree( Integers, -17 ); 17
EuclideanDegree
calls R.operations.EuclideanDegree( R, r )
and
returns the value.
The default function called this way is RingOps.EuclideanDegree
, which
justs signals an error, because there is no default way to compute the
Euclidean degree of an element. Thus Euclidean rings must overlay this
default function with other functions.
EuclideanRemainder( r, m )
EuclideanRemainder( R, r, m )
In the first form EuclideanRemainder
returns the remainder of the ring
element r modulo the ring element m in their default ring. In the
second form EuclideanRemainder
returns the remainder of the ring
element r modulo the ring element m in the ring R. The ring R
must be a Euclidean ring (see IsEuclideanRing) otherwise an error is
signalled.
A ring R is called a Euclidean ring, if it is an integral ring, and
there exists a function δ, called the Euclidean degree, from
R-{0R} to the nonnegative integers, such that for every pair r ∈
R and s ∈ R-{0R} there exists an element q such that either r
- q s = 0R or δ(r - q s) < δ( s ). The existence of this
division with remainder implies that the Euclidean algorithm can be
applied to compute a greatest common divisors of two elements, which in
turn implies that R is a unique factorization ring.
EuclideanRemainder
returns this remainder r - q s.
gap> EuclideanRemainder( 16, 3 ); 1 gap> EuclideanRemainder( Integers, 201, 11 ); 3
EuclideanRemainder
calls R.operations.EuclideanRemainder( R, r,
m )
in order to compute the remainder and returns the value.
The default function called this way uses QuotientRemainder
in order to
compute the remainder.
EuclideanQuotient( r, m )
EuclideanQuotient( R, r, m )
In the first form EuclideanQuotient
returns the Euclidean quotient of
the ring elements r and m in their default ring. In the second form
EuclideanQuotient
returns the Euclidean quotient of the ring elements
rand m in the ring R. The ring R must be a Euclidean ring (see
IsEuclideanRing) otherwise an error is signalled.
A ring R is called a Euclidean ring, if it is an integral ring, and
there exists a function δ, called the Euclidean degree, from
R-{0R} to the nonnegative integers, such that for every pair r ∈
R and s ∈ R-{0R} there exists an element q such that either r
- q s = 0R or δ(r - q s) < δ( s ). The existence of this
division with remainder implies that the Euclidean algorithm can be
applied to compute a greatest common divisors of two elements, which in
turn implies that R is a unique factorization ring.
EuclideanQuotient
returns the quotient q.
gap> EuclideanQuotient( 16, 3 ); 5 gap> EuclideanQuotient( Integers, 201, 11 ); 18
EuclideanQuotient
calls R.operations.EuclideanQuotient( R, r,
m )
and returns the value.
The default function called this way uses QuotientRemainder
in order to
compute the quotient.
QuotientRemainder( r, m )
QuotientRemainder( R, r, m )
In the first form QuotientRemainder
returns the Euclidean quotient and
the Euclidean remainder of the ring elements r and m in their default
ring as pair of ring elements. In the second form QuotientRemainder
returns the Euclidean quotient and the Euclidean remainder of the ring
elements r and m in the ring R. The ring R must be a Euclidean
ring (see IsEuclideanRing) otherwise an error is signalled.
A ring R is called a Euclidean ring, if it is an integral ring, and
there exists a function δ, called the Euclidean degree, from
R-{0R} to the nonnegative integers, such that for every pair r ∈
R and s ∈ R-{0R} there exists an element q such that either r
- q s = 0R or δ(r - q s) < δ( s ). The existence of this
division with remainder implies that the Euclidean algorithm can be
applied to compute a greatest common divisors of two elements, which in
turn implies that R is a unique factorization ring.
QuotientRemainder
returns this quotient q and the remainder r - q
s.
gap> qr := QuotientRemainder( 16, 3 ); [ 5, 1 ] gap> 3 * qr[1] + qr[2]; 16 gap> QuotientRemainder( Integers, 201, 11 ); [ 18, 3 ]
QuotientRemainder
calls R.operations.QuotientRemainder( R, r,
m )
and returns the value.
The default function called this way is RingOps.QuotientRemainder
,
which just signals an error, because there is no default function to
compute the Euclidean quotient or remainder of one ring element modulo
another. Thus Euclidean rings must overlay this default function with
other functions.
Mod( r, m )
Mod( R, r, m )
Mod
is a synonym for EuclideanRemainder
and is obsolete, see
EuclideanRemainder.
QuotientMod( r, s, m )
QuotientMod( R, r, s, m )
In the first form QuotientMod
returns the quotient of the ring elements
r and s modulo the ring element m in their default ring (see
DefaultRing). In the second form QuotientMod
returns the quotient of
the ring elements r and s modulo the ring element m in the ring
R. R must be a Euclidean ring (see IsEuclideanRing) so that
EuclideanRemainder
(see EuclideanRemainder) can be applied. If the
modular quotient does not exist, false
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 divisable by m in R and that q is either 0 (if r is divisable by m) or the Euclidean degree of q is strictly smaller than the Euclidean degree of m.
gap> QuotientMod( Integers, 13, 7, 11 ); 5 gap> QuotientMod( Integers, 13, 7, 21 ); false
QuotientMod
calls R.operations.QuotientMod( R, r, s, m )
and returns the value.
The default function called this way is RingOps.QuotientMod
, which
applies the Euclidean gcd algorithm to compute the gcd g of s and
m, together with the representation of this gcd as linear combination
in s and m, g = a * s + b * m
. The modular quotient
exists if and only if r is divisible by g, in which case the quotient
is a * Quotient( R, r, g )
. This default function is seldom
overlaid, because there is seldom a better way to compute the quotient.
PowerMod( r, e, m )
PowerMod( R, r, e, m )
In the first form PowerMod
returns the e-th power of the ring element
r modulo the ring element m in their default ring (see
DefaultRing). In the second form PowerMod
returns the e-th power
of the ring element r modulo the ring element m in the ring R. 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 re 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( Integers, 2, 20, 100 ); 76 # 220 = 1048576 gap> PowerMod( Integers, 3, 2^32, 2^32+1 ); 3029026160 # which proves that 232+1 is not a prime gap> PowerMod( Integers, 3, -1, 22 ); 15 # 3*15 = 45 = 1 modulo 22
PowerMod
calls R.operations.PowerMod( R, r, e, m )
and
returns the value.
The default function called this way is RingOps.PowerMod
, which uses
QuotientMod
(see QuotientMod) if necessary to invert r, and then
uses a right-to-left repeated squaring, reducing the intermediate results
modulo m in each step. This function is seldom overlaid, because there
is seldom a better way of computing the power.
Gcd( r1, r2... )
Gcd( R, r1, r2... )
In the first form Gcd
returns the greatest common divisor of the ring
elements r1, r2... etc. in their default ring (see DefaultRing).
In the second form Gcd
returns 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 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 r1, r2... etc. of the ring R is an element of largest Euclidean degree (see EuclideanDegree) that is a divisor of r1, r2... etc. We define gcd( r, 0R ) = gcd( 0R, r ) = StandardAssociate( r ) and gcd( 0R, 0R ) = 0R.
gap> Gcd( Integers, 123, 66 ); 3
Gcd
calls R.operations.Gcd
repeatedly, each time passing the 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.Gcd
, which applies the
Euclidean algorithm to compute the greatest common divisor. Special
categories of rings overlay this default function with more efficient
functions.
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 r1, r2... etc. of a ring R is a list of ring elements s1, s2... etc. of R, such that g = s1 r1 + s2 r2 .... 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.
Lcm( r1, r2... )
Lcm( R, r1, r2... )
In the first form Lcm
returns the least common multiple of the ring
elements r1, r2... etc. in their default ring (see DefaultRing).
In the second form Lcm
returns the least common multiple 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. Lcm
returns the standard associate (see
StandardAssociate) of the least common multiples.
A least common multiple of the elements r1, r2... etc. of the ring R is an element of smallest Euclidean degree (see EuclideanDegree) that is a multiple of r1, r2... etc. We define lcm( r, 0R ) = lcm( 0R, r ) = StandardAssociate( r ) and Lcm( 0R, 0R ) = 0R.
Lcm
uses the equality lcm(m,n) = m*n / gcd(m,n) (see Gcd).
gap> Lcm( Integers, 123, 66 ); 2706
Lcm
calls R.operations.Lcm
repeatedly, each time passing the 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.Lcm
, which simply
returns the product of r with the quotient of s and the greatest
common divisor of r and s. Special categories of rings overlay this
default function with more efficient functions.
A ring R is represented by a record with the following entries.
isDomain
:true
.
isRing
:true
.
isCommutativeRing
:true
if the multiplication is known to be commutative,
false
if the multiplication is known to be noncommutative, and
unbound otherwise.
isIntegralRing
:true
if R is known to be a commutative domain with 1
without zero divisor, false
if R is known to lack one of
these properties, and unbound otherwise.
isUniqueFactorizationRing
:true
if R is known to be a domain with unique
factorization into primes, false
if R is known to have a
nonunique factorization, and unbound otherwise.
isEuclideanRing
:true
if R is known to be a Euclidean domain, false
if it
is known not to be a Euclidean domain, and unbound otherwise.
zero
:
units
:
size
:
one
:
integralBase
:
As an example of a ring record, here is the definition of the ring record
Integers
.
rec( # category components isDomain := true, isRing := true, # identity components generators := [ 1 ], zero := 0, one := 1, name := "Integers", # knowledge components size := "infinity", isFinite := false, isCommutativeRing := true, isIntegralRing := true, isUniqueFactorizationRing := true, isEuclideanRing := true, units := [ -1, 1 ], # operations record operations := rec( ... IsPrime := function ( Integers, n ) return IsPrimeInt( n ); end, ... 'mod' := function ( Integers, n, m ) return n mod m; end, ... ) )
gap3-jm