# 1.30 About Defining New Group Elements

In this section we will show how one can add a new type of group elements to GAP. A lot of group elements in GAP are implemented this way, for example elements of generic factor groups, or elements of generic direct products.

We will use prime residue classes modulo an integer as our example. They have the advantage that the arithmetic is very simple, so that we can concentrate on the implementation without being carried away by mathematical details.

Note that everything we define is already in the library in the file LIBNAME/"numtheor.g", so there is no need for you to type it in. You may however like to make a copy of this file and modify it.

We will represent residue classes by records. This is absolutely typical, all group elements not built into the GAP kernel are realized by records.

To distinguish records representing residue classes from other records we require that residue class records have a component with the name isResidueClass and the value true. We also require that they have a component with the name isGroupElement and again the value true. Those two components are called the tag components.

Next each residue class record must of course have components that tell us which residue class this record represents. The component with the name representative contains the smallest nonnegative element of the residue class. The component with the name modulus contains the modulus. Those two components are called the identifying components.

Finally each residue class record must have a component with the name operations that contains an appropriate operations record (see below). In this way we can make use of the possibility to define operations for records (see Comparisons of Records and Operations for Records).

Below is an example of a residue class record.

    r13mod43 := rec(
isGroupElement := true,
isResidueClass := true,
representative := 13,
modulus        := 43,
domain         := GroupElements,
operations     := ResidueClassOps );

The first function that we have to write is very simple. Its only task is to test whether an object is a residue class. It does this by testing for the tag component isResidueClass.

    gap> IsResidueClass := function ( obj )
>     return IsRec( obj )
>            and IsBound( obj.isResidueClass )
>            and obj.isResidueClass;
> end;;

Our next function takes a representative and a modulus and constructs a new residue class. Again this is not very difficult.

    gap> ResidueClass := function ( representative, modulus )
>     local res;
>     res := rec();
>     res.isGroupElement  := true;
>     res.isResidueClass  := true;
>     res.representative  := representative mod modulus;
>     res.modulus         := modulus;
>     res.domain          := GroupElements;
>     res.operations      := ResidueClassOps;
>     return res;
> end;;

Now we have to define the operations record for residue classes. Remember that this record contains a function for each binary operation, Comparisons of Records and Operations for Records). The operations =, <, *, /, mod, ^, Comm, and Order are the ones that are applicable to all group elements. The meaning of those operations for group elements Operations for Group Elements.

Luckily we do not have to define everything. Instead we can inherit a lot of those functions from generic group elements. For example, for all group elements g/h should be equivalent to g*h^-1. So the function for / could simply be function(g,h) return g*h^-1; end. Note that this function can be applied to all group elements, independently of their type, because all the dependencies are in * and ^.

The operations record GroupElementOps contains such functions that can be used by all types of group elements. Note that there is no element that has GroupElementsOps as its operations record. This is impossible, because there is for example no generic method to multiply or invert group elements. Thus GroupElementsOps is only used to inherit general methods as is done below.

 gap> ResidueClassOps := Copy( GroupElementOps );;

Note that the copy is necessary, otherwise the following assignments would not only change ResidueClassOps but also GroupElementOps.

The first function we are implementing is the equality comparison. The required operation is described simply enough. = should evaluate to true if the operands are equal and false otherwise. Two residue classes are of course equal if they have the same representative and the same modulus. One complication is that when this function is called either operand may not be a residue class. Of course at least one must be a residue class otherwise this function would not have been called at all.

    gap> ResidueClassOps.\= := function ( l, r )
>     local   isEql;
>     if IsResidueClass( l )  then
>         if IsResidueClass( r )  then
>             isEql :=    l.representative = r.representative
>                     and l.modulus        = r.modulus;
>         else
>             isEql := false;
>         fi;
>     else
>         if IsResidueClass( r )  then
>             isEql := false;
>         else
>             Error("panic, neither <l> nor <r> is a residue class");
>         fi;
>     fi;
>     return isEql;
> end;;

Note that the quotes around the equal sign = are necessary, otherwise it would not be taken as a record component name, as required, but as the symbol for equality, which must not appear at this place.

Note that we do not have to implement a function for the inequality operator <, because it is in the GAP kernel implemented by the equivalence l < r is not l = r.

The next operation is the comparison. We define that one residue class is smaller than another residue class if either it has a smaller modulus or, if the moduli are equal, it has a smaller representative. We must also implement comparisons with other objects.

    gap> ResidueClassOps.\< := function ( l, r )
>     local   isLess;
>     if IsResidueClass( l )  then
>         if IsResidueClass( r )  then
>             isLess :=   l.representative < r.representative
>                     or (l.representative = r.representative
>                         and l.modulus    < r.modulus);
>         else
>             isLess := not IsInt( r ) and not IsRat( r )
>                   and not IsCyc( r ) and not IsPerm( r )
>                   and not IsWord( r ) and not IsAgWord( r );
>         fi;
>     else
>         if IsResidueClass( r )  then
>             isLess :=  IsInt( l ) or IsRat( l )
>                     or IsCyc( l ) or IsPerm( l )
>                     or IsWord( l ) or IsAgWord( l );
>         else
>             Error("panic, neither <l> nor <r> is a residue class");
>         fi;
>     fi;
>     return isLess;
> end;;

The next operation that we must implement is the multiplication *. This function is quite complex because it must handle several different tasks. To make its implementation easier to understand we will start with a very simple--minded one, which only multiplies residue classes, and extend it in the following paragraphs.

    gap> ResidueClassOps.\* := function ( l, r )
>     local   prd;        # product of l and r, result
>     if IsResidueClass( l )  then
>         if IsResidueClass( r )  then
>             if l.modulus <> r.modulus  then
>                 Error("<l> and <r> must have the same modulus");
>             fi;
>             prd := ResidueClass(
>                         l.representative * r.representative,
>                         l.modulus );
>         else
>             Error("product of <l> and <r> must be defined");
>         fi;
>     else
>         if IsResidueClass( r )  then
>             Error("product of <l> and <r> must be defined");
>         else
>             Error("panic, neither <l> nor <r> is a residue class");
>         fi;
>     fi;
>     return prd;
> end;;

This function correctly multiplies residue classes, but there are other products that must be implemented. First every group element can be multiplied with a list of group elements, and the result shall be the Operations for Lists). In such a case the above function would only signal an error, which is not acceptable. Therefore we must extend this definition.

    gap> ResidueClassOps.\* := function ( l, r )
>     local   prd;        # product of l and r, result
>     if IsResidueClass( l )  then
>         if IsResidueClass( r )  then
>             if l.modulus <> r.modulus  then
>                 Error( "<l> and <r> must have the same modulus" );
>             fi;
>             prd := ResidueClass(
>                         l.representative * r.representative,
>                         l.modulus );
>         elif IsList( r )  then
>             prd := List( r, x -> l * x );
>         else
>             Error("product of <l> and <r> must be defined");
>         fi;
>     elif IsList( l )  then
>         if IsResidueClass( r )  then
>             prd := List( l, x -> x * r );
>         else
>             Error("panic: neither <l> nor <r> is a residue class");
>         fi;
>     else
>         if IsResidueClass( r )  then
>             Error( "product of <l> and <r> must be defined" );
>         else
>             Error("panic, neither <l> nor <r> is a residue class");
>         fi;
>     fi;
>     return prd;
> end;;

This function is almost complete. However it is also allowed to multiply a group element with a subgroup and the result shall be a coset (see RightCoset). The operations record of subgroups, which are of course also represented by records (see Group Records), contains a function that constructs such a coset. The problem is that in an expression like subgroup * residue-class, this function is not called. This is because the multiplication function in the operations record of the right operand is called if both operands have such a function (see Operations for Records). Now in the above case both operands have such a function. The left operand subgroup has the operations record GroupOps (or some refinement thereof), the right operand residue-class has the operations record ResidueClassOps. Thus ResidueClassOps.* is called. But it does not and also should not know how to construct a coset. The solution is simple. The multiplication function for residue classes detects this special case and simply calls the multiplication function of the left operand.

    gap> ResidueClassOps.\* := function ( l, r )
>     local   prd;        # product of l and r, result
>     if IsResidueClass( l )  then
>         if IsResidueClass( r )  then
>             if l.modulus <> r.modulus  then
>                 Error( "<l> and <r> must have the same modulus" );
>             fi;
>             prd := ResidueClass(
>                         l.representative * r.representative,
>                         l.modulus );
>         elif IsList( r )  then
>             prd := List( r, x -> l * x );
>         else
>             Error("product of <l> and <r> must be defined");
>         fi;
>     elif IsList( l )  then
>         if IsResidueClass( r )  then
>             prd := List( l, x -> x * r );
>         else
>             Error("panic: neither <l> nor <r> is a residue class");
>         fi;
>     else
>         if IsResidueClass( r )  then
>             if IsRec( l )  and IsBound( l.operations )
>                 and IsBound( l.operations.\* )
>                 and l.operations.\* <> ResidueClassOps.\*
>             then
>                 prd := l.operations.\*( l, r );
>             else
>                 Error("product of <l> and <r> must be defined");
>             fi;
>         else
>             Error("panic, neither <l> nor <r> is a residue class");
>         fi;
>     fi;
>     return prd;
> end;;

Now we are done with the multiplication.

Next is the powering operation ^. It is not very complicated. The PowerMod function (see PowerMod) does most of what we need, especially the inversion of elements with the Euclidean algorithm when the exponent is negative. Note however, that the definition of operations (see Operations for Group Elements) requires that the conjugation is available as power of a residue class by another residue class. This is of course very easy since residue classes form an abelian group.

    gap> ResidueClassOps.\^ := function ( l, r )
>     local    pow;
>     if IsResidueClass( l )  then
>         if IsResidueClass( r )  then
>             if l.modulus <> r.modulus  then
>                 Error("<l> and <r> must have the same modulus");
>             fi;
>             if GcdInt( r.representative, r.modulus ) <> 1  then
>                 Error("<r> must be invertable");
>             fi;
>             pow := l;
>         elif IsInt( r )  then
>             pow := ResidueClass(
>                         PowerMod( l.representative, r, l.modulus ),
>                         l.modulus );
>         else
>             Error("power of <l> and <r> must be defined");
>         fi;
>     else
>         if IsResidueClass( r )  then
>             Error("power of <l> and <r> must be defined");
>         else
>             Error("panic, neither <l> nor <r> is a residue class");
>         fi;
>     fi;
>     return pow;
> end;;

The last function that we have to write is the printing function. This is called to print a residue class. It prints the residue class in the form ResidueClass( representative, modulus ). It is fairly typical to print objects in such a form. This form has the advantage that it can be read back, resulting in exactly the same element, yet it is very concise.

    gap> ResidueClassOps.Print := function ( r )
>     Print("ResidueClass( ",r.representative,", ",r.modulus," )");
> end;;

Now we are done with the definition of residue classes as group elements. Try them. We can at this point actually create groups of such elements, and compute in them.

However, we are not yet satisfied. There are two problems with the code we have implemented so far. Different people have different opinions about which of those problems is the graver one, but hopefully all agree that we should try to attack those problems.

The first problem is that it is still possible to define objects via Group (see Group) that are not actually groups.

    gap> G := Group( ResidueClass(13,43), ResidueClass(13,41) );
Group( ResidueClass( 13, 43 ), ResidueClass( 13, 41 ) ) 

The other problem is that groups of residue classes constructed with the code we have implemented so far are not handled very efficiently. This is because the generic group algorithms are used, since we have not implemented anything else. For example to test whether a residue class lies in a residue class group, all elements of the residue class group are computed by a Dimino algorithm, and then it is tested whether the residue class is an element of this proper set.

To solve the first problem we must first understand what happens with the above code if we create a group with Group( res1, res2... ). Group tries to find a domain that contains all the elements res1, res2, etc. It first calls Domain( [ res1, res2... ] ) (see Domain). Domain looks at the residue classes and sees that they all are records and that they all have a component with the name domain. This is understood to be a domain in which the elements lie. And in fact res1 in GroupElements is true, because GroupElements accepts all records with tag isGroupElement. So Domain returns GroupElements. Group then calls
GroupElements.operations.Group(GroupElements,[res1,res2...],id), where id is the identity residue class, obtained by res1 ^ 0, and returns the result.

GroupElementsOps.Group is the function that actually creates the group. It does this by simply creating a record with its second argument as generators list, its third argument as identity, and the generic GroupOps as operations record. It ignores the first argument, which is passed only because convention dictates that a dispatcher passes the domain as first argument.

So to solve the first problem we must achieve that another function instead of the generic function GroupElementsOps.Group is called. This can be done by persuading Domain to return a different domain. And this will happen if the residue classes hold this other domain in their domain component.

The obvious choice for such a domain is the (yet to be written) domain ResidueClasses. So ResidueClass must be slightly changed.

    gap> ResidueClass := function ( representative, modulus )
>     local res;
>     res := rec();
>     res.isGroupElement  := true;
>     res.isResidueClass  := true;
>     res.representative  := representative mod modulus;
>     res.modulus         := modulus;
>     res.domain          := ResidueClasses;
>     res.operations      := ResidueClassOps;
>     return res;
> end;;

The main purpose of the domain ResidueClasses is to construct groups, so there is very little we have to do. And in fact most of that can be inherited from GroupElements.

    gap> ResidueClasses := Copy( GroupElements );;
gap> ResidueClasses.name := "ResidueClasses";;
gap> ResidueClassesOps := Copy( GroupElementsOps );;
gap> ResidueClasses.operations := ResidueClassesOps;;

So now we must implement ResidueClassesOps.Group, which should check whether the passed elements do in fact form a group. After checking it simply delegates to the generic function GroupElementsOps.Group to create the group as before.

    gap> ResidueClassesOps.Group := function ( ResidueClasses, gens, id )
>     local   g;          # one generator from gens
>     for g  in gens  do
>         if g.modulus <> id.modulus  then
>             Error("the generators must all have the same modulus");
>         fi;
>         if GcdInt( g.representative, g.modulus ) <> 1  then
>           Error("the generators must all be prime residue classes");
>         fi;
>     od;
>     return GroupElementOps.Group( ResidueClasses, gens, id );
> end;;

This solves the first problem. To solve the second problem, i.e., to make operations with residue class groups more efficient, we must extend the function ResidueClassesOps.Group. It now enters a new operations record into the group. It also puts the modulus into the group record, so that it is easier to access.

    gap> ResidueClassesOps.Group := function ( ResidueClasses, gens, id )
>     local   G,          # group G, result
>             gen;        # one generator from gens
>     for gen  in gens  do
>         if gen.modulus <> id.modulus  then
>             Error("the generators must all have the same modulus");
>         fi;
>         if GcdInt( gen.representative, gen.modulus ) <> 1  then
>           Error("the generators must all be prime residue classes");
>         fi;
>     od;
>     G := GroupElementsOps.Group( ResidueClasses, gens, id );
>     G.modulus    := id.modulus;
>     G.operations := ResidueClassGroupOps;
>     return G;
> end;;

Of course now we must build such an operations record. Luckily we do not have to implement all functions, because we can inherit a lot of functions from GroupOps. This is done by copying GroupOps as we have done before for ResidueClassOps and ResidueClassesOps.

 gap> ResidueClassGroupOps := Copy( GroupOps );;

Now the first function that we must write is the Subgroup function to ensure that not only groups constructed by Group have the correct operations record, but also subgroups of those groups created by Subgroup. As in Group we only check the arguments and then leave the work to GroupOps.Subgroup.

    gap> ResidueClassGroupOps.Subgroup := function ( G, gens )
>     local   S,          # subgroup of G, result
>             gen;        # one generator from gens
>     for gen  in gens  do
>         if gen.modulus <> G.modulus  then
>             Error("the generators must all have the same modulus");
>         fi;
>         if GcdInt( gen.representative, gen.modulus ) <> 1  then
>           Error("the generators must all be prime residue classes");
>         fi;
>     od;
>     S := GroupOps.Subgroup( G, gens );
>     S.modulus    := G.modulus;
>     S.operations := ResidueClassGroupOps;
>     return S;
> end;;

The first function that we write especially for residue class groups is SylowSubgroup. Since residue class groups are abelian we can compute a Sylow subgroup of such a group by simply taking appropriate powers of the generators.

    gap> ResidueClassGroupOps.SylowSubgroup := function ( G, p )
>     local   S,          # Sylow subgroup of G, result
>             gen,        # one generator of G
>             ord,        # order of gen
>             gens;       # generators of S
>     gens := [];
>     for gen  in G.generators  do
>         ord := OrderMod( gen.representative, G.modulus );
>         while ord mod p = 0  do ord := ord / p;  od;
>         Add( gens, gen ^ ord );
>     od;
>     S := Subgroup( Parent( G ), gens );
>     return S;
> end;;

To allow the other functions that are applicable to residue class groups to work efficiently we now want to make use of the fact that residue class groups are direct products of cyclic groups and that we know what those factors are and how we can project onto those factors.

To do this we write ResidueClassGroupOps.MakeFactors that adds the components facts, roots, sizes, and sgs to the group record G. This information, detailed below, will enable other functions to work efficiently with such groups. Creating such information is a fairly typical thing, for example for permutation groups the corresponding information is the stabilizer chain computed by MakeStabChain.

G.facts will be the list of prime power factors of G.modulus. Actually this is a little bit more complicated, because the residue class group modulo the largest power q of 2 that divides G.modulus need not be cyclic. So if q is a multiple of 4, G.facts[1] will be 4, corresponding to the projection of G into (Z / 4 Z)^* (of size 2), furthermore if q is a multiple of 8, G.facts[2] will be q, corresponding to the projection of G into the subgroup generated by 5 in (Z / q Z)^* (of size q/4).

G.roots will be a list of primitive roots, i.e., of generators of the corresponding factors in G.facts. G.sizes will be a list of the sizes of the corresponding factors in G.facts, i.e., G.sizes[i] = Phi( G.facts[i] ). (If G.modulus is a multiple of 8, G.roots[2] will be 5, and G.sizes[2] will be q/4.)

Now we can represent each element g of the group G by a list e, called the exponent vector, of the length of G.facts, where e[i] is the logarithm of g.representative mod G.facts[i] with respect to G.roots[i]. The multiplication of elements of G corresponds to the componentwise addition of their exponent vectors, where we add modulo G.sizes[i] in the i-th component. (Again special consideration are necessary if G.modulus is divisible by 8.)

Next we compute the exponent vectors of all generators of G, and represent this information as a matrix. Then we bring this matrix into upper triangular form, with an algorithm that is very much like the ordinary Gaussian elimination, modified to account for the different sizes of the components. This upper triangular matrix of exponent vectors is the component G.sgs. This new matrix obviously still contains the exponent vectors of a generating system of G, but a much nicer one, which allows us to tackle problems one component at a time. (It is not necessary that you fully check this, the important thing here is not the mathematical side.)

    gap> ResidueClassGroupOps.MakeFactors := function ( G )
>     local   p, q,       # prime factor of modulus and largest power
>             r, s,       # two rows of the standard generating system
>             g,          # extended gcd of leading entries in r, s
>             x, y,       # two entries in r and s
>             i, k, l;    # loop variables
>
>     # find the factors of the direct product
>     G.facts := [];
>     G.roots := [];
>     G.sizes := [];
>     for p  in Set( Factors( G.modulus ) )  do
>         q := p;
>         while G.modulus mod (p*q) = 0  do q := p*q;  od;
>         if q mod 4 = 0  then
>         fi;
>         if q mod 8 = 0  then
>         fi;
>         if p <> 2  then
>             Add( G.roots, PrimitiveRootMod( q ) );
>         fi;
>     od;
>
>     # represent each generator in this factorization
>     G.sgs := [];
>     for k  in [ 1 .. Length( G.generators ) ]  do
>         G.sgs[k] := [];
>         for i  in [ 1 .. Length( G.facts ) ]  do
>             if G.facts[i] mod 8 = 0  then
>                 if G.generators[k].representative mod 4 = 1  then
>                     G.sgs[k][i] := LogMod(
>                         G.generators[k].representative,
>                         G.roots[i], G.facts[i] );
>                 else
>                     G.sgs[k][i] := LogMod(
>                         -G.generators[k].representative,
>                         G.roots[i], G.facts[i] );
>                 fi;
>             else
>                 G.sgs[k][i] := LogMod(
>                         G.generators[k].representative,
>                         G.roots[i], G.facts[i] );
>             fi;
>         od;
>     od;
>     for i  in [ Length( G.sgs ) + 1 .. Length( G.facts ) ]  do
>         G.sgs[i] := 0 * G.facts;
>     od;
>
>     # bring this matrix to diagonal form
>     for i  in [ 1 .. Length( G.facts ) ]  do
>         r := G.sgs[i];
>         for k  in [ i+1 .. Length( G.sgs ) ]  do
>             s := G.sgs[k];
>             g := Gcdex( r[i], s[i] );
>             for l  in [ i .. Length( r ) ]  do
>                 x := r[l];  y := s[l];
>                 r[l] := (g.coeff1 * x + g.coeff2 * y) mod G.sizes[l];
>                 s[l] := (g.coeff3 * x + g.coeff4 * y) mod G.sizes[l];
>             od;
>         od;
>         s := [];
>         x := G.sizes[i] / GcdInt( G.sizes[i], r[i] );
>         for l  in [ 1 .. Length( r ) ]  do
>             s[l] := (x * r[l]) mod G.sizes[l];
>         od;
>     od;
>
> end;;

With the information computed by MakeFactors it is now of course very easy to compute the size of a residue class group. We just look at the G.sgs, and multiply the orders of the leading exponents of the nonzero exponent vectors.

    gap> ResidueClassGroupOps.Size := function ( G )
>     local   s,          # size of G, result
>             i;          # loop variable
>     if not IsBound( G.facts )  then
>         G.operations.MakeFactors( G );
>     fi;
>     s := 1;
>     for i  in [ 1 .. Length( G.facts ) ]  do
>         s := s * G.sizes[i] / GcdInt( G.sizes[i], G.sgs[i][i] );
>     od;
>     return s;
> end;;

The membership test is a little bit more complicated. First we test that the first argument is really a residue class with the correct modulus. Then we compute the exponent vector of this residue class and reduce this exponent vector using the upper triangular matrix G.sgs.

    gap> ResidueClassGroupOps.\in := function ( res, G )
>     local   s,          # exponent vector of res
>             g,          # extended gcd
>             x, y,       # two entries in s and G.sgs[i]
>             i, l;       # loop variables
>     if not IsResidueClass( res )
>         or res.modulus <> G.modulus
>         or GcdInt( res.representative, res.modulus ) <> 1
>     then
>         return false;
>     fi;
>     if not IsBound( G.facts )  then
>         G.operations.MakeFactors( G );
>     fi;
>     s := [];
>     for i  in [ 1 .. Length( G.facts ) ]  do
>         if G.facts[i] mod 8 = 0  then
>             if res.representative mod 4 = 1  then
>                 s[i] := LogMod( res.representative,
>                                 G.roots[i], G.facts[i] );
>             else
>                 s[i] := LogMod( -res.representative,
>                                 G.roots[i], G.facts[i] );
>             fi;
>         else
>             s[i] := LogMod( res.representative,
>                             G.roots[i], G.facts[i] );
>         fi;
>     od;
>     for i  in [ 1 .. Length( G.facts ) ]  do
>         if s[i] mod GcdInt( G.sizes[i], G.sgs[i][i] ) <> 0  then
>             return false;
>         fi;
>         g := Gcdex( s[i], G.sgs[i][i] );
>         for l  in [ i .. Length( G.facts ) ]  do
>             x := s[l];  y := G.sgs[i][l];
>             s[l] := (g.coeff3 * x + g.coeff4 * y) mod G.sizes[l];
>         od;
>     od;
>     return true;
> end;;

We also add a function Random that works by creating a random exponent as a random linear combination of the exponent vectors in G.sgs, and converts this exponent vector to a residue class. (The main purpose of this function is to allow you to create random test examples for the other functions.)

    gap> ResidueClassGroupOps.Random := function ( G )
>     local   s,          # exponent vector of random element
>             r,          # vector of remainders in each factor
>             i, k, l;    # loop variables
>     if not IsBound( G.facts )  then
>         G.operations.MakeFactors( G );
>     fi;
>     s := 0 * G.facts;
>     for i  in [ 1 .. Length( G.facts ) ]  do
>         l := G.sizes[i] / GcdInt( G.sizes[i], G.sgs[i][i] );
>         k := Random( [ 0 .. l-1 ] );
>         for l  in [ i .. Length( s ) ]  do
>             s[l] := (s[l] + k * G.sgs[i][l]) mod G.sizes[l];
>         od;
>     od;
>     r := [];
>     for l  in [ 1 .. Length( s ) ]  do
>         r[l] := PowerModInt( G.roots[l], s[l], G.facts[l] );
>         if G.facts[l] mod 8 = 0  and r[1] = 3  then
>             r[l] := G.facts[l] - r[l];
>         fi;
>     od;
>     return ResidueClass( ChineseRem( G.facts, r ), G.modulus );
> end;;

There are a lot more functions that would benefit from being implemented especially for residue class groups. We do not show them here, because the above functions already displayed how such functions can be written.

To round things up, we finally add a function that constructs the full residue class group given a modulus m. This function is totally independent of the implementation of residue classes and residue class groups. It only has to find a (minimal) system of generators of the full prime residue classes group, and to call Group to construct this group. It also adds the information entry size to the group record, of course with the value phi(n).

    gap> PrimeResidueClassGroup := function ( m )
>     local   G,          # group Z/mZ, result
>             gens,       # generators of G
>             p, q,       # prime and prime power dividing m
>             r,          # primitive root modulo q
>             g;          # is = r mod q and = 1 mod m/q
>
>     # add generators for each prime power factor q of m
>     gens := [];
>     for p  in Set( Factors( m ) )  do
>         q := p;
>         while m mod (q * p) = 0  do q := q * p;  od;
>
>         # (Z/4Z)^* = < 3 >
>         if   q = 4  then
>             r := 3;
>             g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
>             Add( gens, ResidueClass( g, m ) );
>
>         # (Z/8nZ)^* = < 5, -1 > is not cyclic
>         elif q mod 8 = 0  then
>             r := q-1;
>             g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
>             Add( gens, ResidueClass( g, m ) );
>             r := 5;
>             g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
>             Add( gens, ResidueClass( g, m ) );
>
>         # for odd q, (Z/qZ)^* is cyclic
>         elif q <> 2  then
>             r :=  PrimitiveRootMod( q );
>             g := r + q * (((1/q mod (m/q)) * (1 - r)) mod (m/q));
>             Add( gens, ResidueClass( g, m ) );
>         fi;
>
>     od;
>
>     # return the group generated by gens
>     G := Group( gens, ResidueClass( 1, m ) );
>     G.size := Phi( n );
>     return G;
> end;;

There is one more thing that we can learn from this example. Mathematically a residue class is not only a group element, but a set as well. We can reflect this in GAP by turning residue classes into domains (see Domains). Section About Defining New Domains gives an example of how to implement a new domain, so we will here only show the code with few comments.

First we must change the function that constructs a residue class, so that it enters the necessary fields to tag this record as a domain. It also adds the information that residue classes are infinite.

    gap> ResidueClass := function ( representative, modulus )
>     local res;
>     res := rec();
>     res.isGroupElement  := true;
>     res.isDomain        := true;
>     res.isResidueClass  := true;
>     res.representative  := representative mod modulus;
>     res.modulus         := modulus;
>     res.isFinite        := false;
>     res.size            := "infinity";
>     res.domain          := ResidueClasses;
>     res.operations      := ResidueClassOps;
>     return res;
> end;;

The initialization of the ResidueClassOps record must be changed too, because now we want to inherit both from GroupElementsOps and DomainOps. This is done by the function MergedRecord, which takes two records and returns a new record that contains all components from either record.

Note that the record returned by MergedRecord does not have those components that appear in both arguments. This forces us to explicitly write down from which record we want to inherit those functions, or to define them anew. In our example the components common to GroupElementOps and DomainOps are only the equality and ordering functions, which we have to define anyhow. (This solution for the problem of which definition to choose in the case of multiple inheritance is also taken by C++.)

With this function definition we can now initialize ResidueClassOps.

 gap> ResidueClassOps := MergedRecord( GroupElementOps, DomainOps );;

Now we add all functions to this record as described above.

Next we add a function to the operations record that tests whether a certain object is in a residue class.

    gap> ResidueClassOps.\in := function ( element, class )
>     if IsInt( element )  then
>         return (element mod class.modulus = class.representative);
>     else
>         return false;
>     fi;
> end;;

Finally we add a function to compute the intersection of two residue classes.

    gap> ResidueClassOps.Intersection := function ( R, S )
>     local   I,          # intersection of R and S, result
>             gcd;        # gcd of the moduli
>     if IsResidueClass( R )  then
>         if IsResidueClass( S )  then
>             gcd := GcdInt( R.modulus, S.modulus );
>             if     R.representative mod gcd
>                 <> S.representative mod gcd
>             then
>                 I := [];
>             else
>                 I := ResidueClass(
>                         ChineseRem(
>                             [ R.modulus,        S.modulus ] ,
>                             [ R.representative, S.representative ]),
>                         Lcm(  R.modulus,        S.modulus ) );
>             fi;
>         else
>             I := DomainOps.Intersection( R, S );
>         fi;
>     else
>         I := DomainOps.Intersection( R, S );
>     fi;
>     return I;
> end;;

There is one further thing that we have to do. When Group is called with a single argument that is a domain, it assumes that you want to create a new group such that there is a bijection between the original domain and the new group. This is not what we want here. We want that in this case we get the cyclic group that is generated by the single residue class. (This overloading of Group is probably a mistake, but so is the overloading of residue classes, which are both group elements and domains.) The following definition solves this problem.

    gap> ResidueClassOps.Group := function ( R )
>     return ResidueClassesOps.Group( ResidueClasses, [R], R^0 );
> end;;

This concludes our example. There are however several further things that you could do. One is to add functions for the quotient, the modulus, etc. Another is to fix the functions so that they do not hang if asked for the residue class group mod 1. Also you might try to implement residue class rings analogous to residue class groups. Finally it might be worthwhile to improve the speed of the multiplication of prime residue classes. This can be done by doing some precomputation in ResidueClass and adding some information to the residue class record for prime residue classes (Mon85).

GAP 3.4.4
April 1997