5.1 A First Attempt to Implement Elements of Residue Class Rings

Suppose we want to do computations with elements of a ring Z/nZ, where n is a positive integer.

First we have to decide how to represent the element k + nZ in GAP. If the modulus n is fixed then we can use the integer k. More precisely, we can use any integer k^¢ such that k - k^¢ is a multiple of n. If different moduli are likely to occur then using a list of the form [ k, n ], or a record of the form rec( residue := k, modulus := n ) is more appropriate. In the following, let us assume the list representation [ k, n ] is chosen. Moreover, we decide that the residue k in all such lists satisfies 0 £ k < n, i.e., the result of adding two residue classes represented by [ k₁, n ] and [ k₂, n ] (of course with same modulus n) will be [ k, n ] with k₁ + k₂ congruent to k modulo n and 0 £ k < n.

Now we can implement the arithmetic operations for residue classes. Note that the result of the mod operator is normalized as required. The division by a noninvertible residue class results in fail.

resclass_sum := function( c1, c2 )
    if c1[2] <> c2[2] then Error( "different moduli" ); fi;
    return [ ( c1[1] + c2[1] ) mod c1[2], c1[2] ];
end;

resclass_diff := function( c1, c2 )
    if c1[2] <> c2[2] then Error( "different moduli" ); fi;
    return [ ( c1[1] - c2[1] ) mod c1[2], c1[2] ];
end;

resclass_prod := function( c1, c2 )
    if c1[2] <> c2[2] then Error( "different moduli" ); fi;
    return [ ( c1[1] * c2[1] ) mod c1[2], c1[2] ];
end;

resclass_quo := function( c1, c2 )
    local quo;
    if c1[2] <> c2[2] then Error( "different moduli" ); fi;
    quo:= QuotientMod( c1[1], c2[1], c1[2] );
    if quo <> fail then
      quo:= [ quo, c1[2] ];
    fi;
    return quo;
end;

gap> list:= List( [ 0 .. 3 ], k -> [ k, 4 ] );
[ [ 0, 4 ], [ 1, 4 ], [ 2, 4 ], [ 3, 4 ] ]
gap> resclass_sum( list[2], list[4] );
[ 0, 4 ]
gap> resclass_diff( list[1], list[2] );
[ 3, 4 ]
gap> resclass_prod( list[2], list[4] );
[ 3, 4 ]
gap> resclass_prod( list[3], list[4] );
[ 2, 4 ]
gap> List( list, x -> resclass_quo( list[2], x ) );
[ fail, [ 1, 4 ], fail, [ 3, 4 ] ]

[Top] [Up] [Next] [Index]