%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A ring.tex GAP documentation Martin Schoenert %% %A @(#)$Id: ring.tex,v 3.9 1993/05/04 11:39:24 fceller Rel $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file describes the polymorphic functions for rings. %% %H $Log: ring.tex,v $ %H Revision 3.9 1993/05/04 11:39:24 fceller %H fixed a spelling error %H %H Revision 3.8 1993/03/11 10:25:17 fceller %H added 'EuclideanQuotient', 'EuclideanRemainder' and 'QuotientRemainder' %H %H Revision 3.7 1993/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.6 1993/02/15 10:15:08 felsch %H more examples fixed %H %H Revision 3.5 1993/02/12 17:20:54 felsch %H examples adjusted to line length 72 %H %H Revision 3.4 1992/04/06 15:03:15 martin %H fixed some more typos %H %H Revision 3.3 1992/04/06 00:10:10 martin %H removed the chapter about polynomials %H %H Revision 3.2 1992/03/11 16:06:31 sam %H renamed chapter "Number Fields" to "Subfields of Cyclotomic Fields" %H %H Revision 3.1 1992/03/11 09:28:07 martin %H added an example of a ring record %H %H Revision 3.0 1991/12/27 16:10:27 martin %H initial revision under RCS %H %% \Chapter{Rings} 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 $0_R$. $(R-\{0_R\},\*)$ must be a monoid. If this monoid has an identity element it is called $1_R$. 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\"'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsRing} 'IsRing( )' 'IsRing' returns 'true' if the object is a ring record, representing a ring (see "Ring Records"), and 'false' otherwise. More precisely 'IsRing' tests whether 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 fool 'IsRing' | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Ring} 'Ring( , ... )'\\ 'Ring( )' In the first form 'Ring' returns the smallest ring that contains all the elements , ... etc. In the second form 'Ring' returns the smallest ring that contains all the elements in the 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{DefaultRing} 'DefaultRing( , ... )' \\ 'DefaultRing( )' In the first form 'DefaultRing' returns the default ring that contains all the elements , ... etc. In the second form 'DefaultRing' returns the default ring that contains all the elements in the 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Comparisons of Ring Elements} ' = ' \\ ' \<> ' The equality operator '=' evaluates to 'true' if the two ring elements and are equal, and to 'false' otherwise. The inequality operator '\<>' evaluates to 'true' if the two ring elements and 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. ' \<\ ' \\ ' \<= ' \\ ' > ' \\ ' >= ' The operators '\<', '\<=', '>', and '>=' evaluate to 'true' if the ring element is less than, less than or equal to, greater than, or greater than or equal to the ring element , 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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. ' + ' The operator '+' evaluates to the sum of the two ring elements and , which must lie in compatible rings. ' - ' The operator '-' evaluates to the difference of the two ring elements and , which must lie in compatible rings. ' \*\ ' The operator '\*' evaluates to the product of the two ring elements and , which must lie in compatible rings. ' \^\ ' The operator '\^' evaluates to the -th power of the ring element . If is a positive integer then '\^' is '\*\*..\*' ( factors). If is a negative integer '\^' is defined as $1 / {^{-}}$. 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"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Quotient} 'Quotient( , )' \\ 'Quotient( , , )' In the first form 'Quotient' returns the quotient of the two ring elements and in their default ring (see "DefaultRing"). In the second form 'Quotient' returns the quotient of the two ring elements and in the ring . It returns 'false' if the quotient does not exist. | gap> Quotient( 4, 2 ); 2 gap> Quotient( Integers, 3, 2 ); false | 'Quotient' calls '.operations.Quotient( , , )' 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsCommutativeRing} 'IsCommutativeRing( )' 'IsCommutativeRing' returns 'true' if the ring 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 '.isCommutativeRing' is bound. If the flag is bound, it returns this value. Otherwise it calls '.operations.IsCommutativeRing( )', remembers the returned value in '.isCommutativeRing', and returns it. The default function called this way is 'RingOps.IsCommutativeRing', which tests whether all the generators commute if the component '.generators' is bound, and tests whether all elements commute otherwise, unless is infinite. This function is seldom overlaid, because most rings already have the flag bound. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsIntegralRing} 'IsIntegralRing( )' 'IsIntegeralRing' returns 'true' if the ring 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 = 0_R$ implies that either $r$ or $s$ is $0_R$. | gap> IsIntegralRing( Integers ); true | 'IsIntegralRing' first tests whether the flag '.isIntegralRing' is bound. If the flag is bound, it returns this value. Otherwise it calls '.operations.IsIntegralRing( )', remembers the returned value in '.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 is infinite. This function is seldom overlaid, because most rings already have the flag bound. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsUniqueFactorizationRing} 'IsUniqueFactorizationRing( )' 'IsUniqueFactorizationRing' returns 'true' if is a unique factorization ring and 'false' otherwise. A ring 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 '.isUniqueFactorizationRing' is bound. If the flag is bound, it returns this value. If this flag has no assigned value it calls the function '.operations.IsUniqueFactorizationRing( )', remembers the returned value in '.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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsEuclideanRing} 'IsEuclideanRing( )' 'IsEuclideanRing' returns 'true' if the ring 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 $\delta$, called the Euclidean degree, from $R-\{0_R\}$ to the nonnegative integers, such that for every pair $r \in R$ and $s \in R-\{0_R\}$ there exists an element $q$ such that either $r - q s = 0_R$ or $\delta(r - q s) \< \delta( 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 '.isEuclideanRing' is bound. If the flag is bound, it returns this value. Otherwise it calls '.operations.IsEuclideanRing( )', remembers the returned value in '.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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsUnit} 'IsUnit( )'\\ 'IsUnit( , )' In the first form 'IsUnit' returns 'true' if the ring element is a unit in its default ring (see "DefaultRing"). In the second form 'IsUnit' returns 'true' if is a unit in the ring . 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 '.operations.IsUnit( , )' and returns the value. The default function called this way is 'RingOps.IsUnit', which tries to compute the inverse of with '.operations.Quotient( , .one, )' and returns 'true' if the result is not 'false', and 'false' otherwise. Special categories of rings overlay this default function with more efficient functions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Units} 'Units( )' 'Units' returns the group of units of the ring . 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 '.units' is bound. If the component is bound, it returns this value. Otherwise it calls '.operations.Units( )', remembers the returned value in '.units', and returns it. The default function called this way is 'RingOps.Units', which runs over all elements of and tests for each whether it is a unit, provided that is finite. Special categories of rings overlay this default function with more efficient functions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsAssociated} 'IsAssociated( , )' \\ 'IsAssociated( , , )' In the first form 'IsAssociated' returns 'true' if the two ring elements and are associated in their default ring (see "DefaultRing") and 'false' otherwise. In the second form 'IsAssociated' returns 'true' if the two ring elements and are associated in the ring 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 '.operations.IsAssociated( , , )' and returns the value. The default function called this way is 'RingOps.IsAssociated', which tries to compute the quotient of and and returns 'true' if the quotient exists and is a unit. Special categories of rings overlay this default function with more efficient functions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{StandardAssociate} 'StandardAssociate( )' \\ 'StandardAssociate( , )' In the first form 'StandardAssociate' returns the standard associate of the ring element in its default ring (see "DefaultRing"). In the second form 'StandardAssociate' returns the standard associate of the ring element in the ring . 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 '.operations.StandardAssociate( , )' 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Associates} 'Associates( )' \\ 'Associates( , )' In the first form 'Associates' returns the set of associates of the ring element in its default ring (see "DefaultRing"). In the second form 'Associates' returns the set of associates of in the ring . 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 '.operations.Associates( , )' and returns the value. The default function called this way is 'RingOps.Associates', which multiplies the set of units of with the element , and returns the set of those elements. Special categories of rings overlay this default function with more efficient functions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsIrreducible} 'IsIrreducible( )'\\ 'IsIrreducible( , )' In the first form 'IsIrreducible' returns 'true' if the ring element is irreducible in its default ring (see "DefaultRing") and 'false' otherwise. In the second form 'IsIrreducible' returns 'true' if the ring element is irreducible in the ring 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 '.operations.IsIrreducible( , )' 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsPrime} 'IsPrime( )' \\ 'IsPrime( , )' In the first form 'IsPrime' returns 'true' if the ring element is a prime in its default ring (see "DefaultRing") and 'false' otherwise. In the second form 'IsPrime' returns 'true' if the ring element is a prime in the ring 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 '.operations.IsPrime( , )' 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Factors} 'Factors( )' \\ 'Factors( , )' In the first form 'Factors' returns the factorization of the ring element in its default ring (see "DefaultRing"). In the second form 'Factors' returns the factorization of the ring element in the ring . 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( , ) ) = '. This list is usually also sorted, thus smallest prime factors come first. If is a unit or zero, 'Factors( , ) = [ ]'. | 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 '.operations.Factors( , )' 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{EuclideanDegree} 'EuclideanDegree( )' \\ 'EuclideanDegree( , )' In the first form 'EuclideanDegree' returns the Euclidean degree of the ring element in its default ring. In the second form 'EuclideanDegree' returns the Euclidean degree of the ring element in the ring . 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 $\delta$, called the Euclidean degree, from $R-\{0_R\}$ to the nonnegative integers, such that for every pair $r \in R$ and $s \in R-\{0_R\}$ there exists an element $q$ such that either $r - q s = 0_R$ or $\delta(r - q s) \< \delta( 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 '.operations.EuclideanDegree( , )' 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{EuclideanRemainder} 'EuclideanRemainder( , )' \\ 'EuclideanRemainder( , , )' In the first form 'EuclideanRemainder' returns the remainder of the ring element modulo the ring element in their default ring. In the second form 'EuclideanRemainder' returns the remainder of the ring element modulo the ring element in the ring . The ring 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 $\delta$, called the Euclidean degree, from $R-\{0_R\}$ to the nonnegative integers, such that for every pair $r \in R$ and $s \in R-\{0_R\}$ there exists an element $q$ such that either $r - q s = 0_R$ or $\delta(r - q s) \< \delta( 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 '.operations.EuclideanRemainder( , , )' in order to compute the remainder and returns the value. The default function called this way uses 'QuotientRemainder' in order to compute the remainder. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{EuclideanQuotient} 'EuclideanQuotient( , )' \\ 'EuclideanQuotient( , , )' In the first form 'EuclideanQuotient' returns the Euclidean quotient of the ring elements and in their default ring. In the second form 'EuclideanQuotient' returns the Euclidean quotient of the ring elements and in the ring . The ring 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 $\delta$, called the Euclidean degree, from $R-\{0_R\}$ to the nonnegative integers, such that for every pair $r \in R$ and $s \in R-\{0_R\}$ there exists an element $q$ such that either $r - q s = 0_R$ or $\delta(r - q s) \< \delta( 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 '.operations.EuclideanQuotient( , , )' and returns the value. The default function called this way uses 'QuotientRemainder' in order to compute the quotient. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{QuotientRemainder} 'QuotientRemainder( , )' \\ 'QuotientRemainder( , , )' In the first form 'QuotientRemainder' returns the Euclidean quotient and the Euclidean remainder of the ring elements and 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 and in the ring . The ring 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 $\delta$, called the Euclidean degree, from $R-\{0_R\}$ to the nonnegative integers, such that for every pair $r \in R$ and $s \in R-\{0_R\}$ there exists an element $q$ such that either $r - q s = 0_R$ or $\delta(r - q s) \< \delta( 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 '.operations.QuotientRemainder( , , )' 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Mod} 'Mod( , )' \\ 'Mod( , , )' 'Mod' is a synonym for 'EuclideanRemainder' and is obsolete, see "EuclideanRemainder". %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{QuotientMod} 'QuotientMod( , , )' \\ 'QuotientMod( , , , )' In the first form 'QuotientMod' returns the quotient of the ring elements and modulo the ring element in their default ring (see "DefaultRing"). In the second form 'QuotientMod' returns the quotient of the ring elements and modulo the ring element in the ring . 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 '.operations.QuotientMod( , , , )' and returns the value. The default function called this way is 'RingOps.QuotientMod', which applies the Euclidean gcd algorithm to compute the gcd of and , together with the representation of this gcd as linear combination in and , ' = \*\ + \*\ '. The modular quotient exists if and only if is divisible by , in which case the quotient is ' \*\ Quotient( , , )'. This default function is seldom overlaid, because there is seldom a better way to compute the quotient. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{PowerMod} 'PowerMod( , , )' \\ 'PowerMod( , , , )' In the first form 'PowerMod' returns the -th power of the ring element modulo the ring element in their default ring (see "DefaultRing"). In the second form 'PowerMod' returns the -th power of the ring element modulo the ring element in the ring . must be an integer. 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( , , -, )'. 'PowerMod' reduces the intermediate values modulo $m$, improving performance drastically when is large and small. | gap> PowerMod( Integers, 2, 20, 100 ); 76 # $2^{20} = 1048576$ gap> PowerMod( Integers, 3, 2^32, 2^32+1 ); 3029026160 # which proves that $2^{32}+1$ is not a prime gap> PowerMod( Integers, 3, -1, 22 ); 15 # 3\*15 = 45 = 1 modulo 22 | 'PowerMod' calls '.operations.PowerMod( , , , )' and returns the value. The default function called this way is 'RingOps.PowerMod', which uses 'QuotientMod' (see "QuotientMod") if necessary to invert , and then uses a right-to-left repeated squaring, reducing the intermediate results modulo in each step. This function is seldom overlaid, because there is seldom a better way of computing the power. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Gcd} 'Gcd( , ... )' \\ 'Gcd( , , ... )' In the first form 'Gcd' returns the greatest common divisor of the ring elements , ... etc. in their default ring (see "DefaultRing"). In the second form 'Gcd' returns the greatest common divisor of the ring elements , ... etc. in the ring . 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_1$, $r_2$... etc. of the ring $R$ is an element of largest Euclidean degree (see "EuclideanDegree") that is a divisor of $r_1$, $r_2$... etc. We define $gcd( r, 0_R ) = gcd( 0_R, r ) = StandardAssociate( r )$ and $gcd( 0_R, 0_R ) = 0_R$. | gap> Gcd( Integers, 123, 66 ); 3 | 'Gcd' calls '.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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{GcdRepresentation} 'GcdRepresentation( , ... )' \\ 'GcdRepresentation( , , ... )' In the first form 'GcdRepresentation' returns the representation of the greatest common divisor of the ring elements , ... etc. in their default ring (see "DefaultRing"). In the second form 'GcdRepresentation' returns the representation of the greatest common divisor of the ring elements , ... etc. in the ring . 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 '.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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Lcm} 'Lcm( , ... )'\\ 'Lcm( , , ... )' In the first form 'Lcm' returns the least common multiple of the ring elements , ... etc. in their default ring (see "DefaultRing"). In the second form 'Lcm' returns the least common multiple of the ring elements , ,... etc. in the ring . 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_1$, $r_2$... etc. of the ring $R$ is an element of smallest Euclidean degree (see "EuclideanDegree") that is a multiple of $r_1$, $r_2$... 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"). | gap> Lcm( Integers, 123, 66 ); 2706 | 'Lcm' calls '.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 with the quotient of and the greatest common divisor of and . Special categories of rings overlay this default function with more efficient functions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Ring Records} A ring is represented by a record with the following entries. 'isDomain':\\ is of course always the value 'true'. 'isRing': \\ is of course always the value 'true'. 'isCommutativeRing': \\ is 'true' if the multiplication is known to be commutative, 'false' if the multiplication is known to be noncommutative, and unbound otherwise. 'isIntegralRing': \\ is 'true' if is known to be a commutative domain with 1 without zero divisor, 'false' if is known to lack one of these properties, and unbound otherwise. 'isUniqueFactorizationRing': \\ is 'true' if is known to be a domain with unique factorization into primes, 'false' if is known to have a nonunique factorization, and unbound otherwise. 'isEuclideanRing': \\ is 'true' if is known to be a Euclidean domain, 'false' if it is known not to be a Euclidean domain, and unbound otherwise. 'zero': \\ is the additive neutral element. 'units': \\ is the list of units of the ring if it is known. 'size': \\ is the size of the ring if it is known. If the ring is not finite this is the string \"infinity\". 'one': \\ is the multiplicative neutral element, if the ring has one. 'integralBase': \\ if the ring is, as additive group, isomorphic to the direct product of a finite number of copies of $Z$ this contains a base. 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, ... ) ) | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section" %% fill-column: 73 %% eval: (hide-body) %% End: %%