[GAP Forum] Bugs in QuotientMod?

Mark Dickinson dickinsm at gmail.com
Fri May 22 09:33:48 BST 2009


Dear all,

I'm not sure whether this is the right place to send bug reports.  Please accept
my apologies if not.

There appear to be a couple of problems with the QuotientMod function.
Here's some output from a GAP session (GAP version 4.4.12, compiled
from source on a 64-bit Linux machine).

gap> x := Indeterminate(Rationals);
x_1
gap> DefaultRing(One(x), Zero(x), x*x+1);
Rationals[x_1]
gap> QuotientMod(One(x), Zero(x), x*x+1);
0

This appears to be telling me that 1/0 is 0 in the ring Q[x]/(x^2+1)
of Gaussian numbers.  I was expecting the QuotientMod call
to return the fail object here, since the documentation for
QuotientMod states:

"If the modular quotient does not exist, `fail' is returned."

I also find the behaviour of QuotientMod for the ring of rational
integers to be rather surprising:

gap> QuotientMod(Integers, 4, 2, 6);
2
gap> QuotientMod(Integers, 4, 8, 6);
ModRat: for <r>/<s> mod <n>, <s>/gcd(<r>,<s>) and <n> must be coprime at
return r / s mod m;
 called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can replace the integer <n> via 'return <n>;' to continue
brk>

The first call succeeds in finding a solution to the associated
congruence 2x = 4 (mod 6), but the second call fails on
what's essentially exactly the same congruence:  8x = 4 (mod 6).

This second oddity in QuotientMod leads to inconsistencies in
division in ZmodnZObj.  For example, let a and b be the residue
classes of 2 and 4 (respectively) modulo 6.  Then GAP allows
division of b by a, but not division of a by b, even though both
the relevant congruences (2x = 4 (mod 6) and 4x = 2 (mod 6))
have exactly two solutions modulo 6.

gap> a := ZmodnZObj(2, 6);
ZmodnZObj( 2, 6 )
gap> b := ZmodnZObj(4, 6);
ZmodnZObj( 4, 6 )
gap> a/b;
ModRat: for <r>/<s> mod <n>, <s>/gcd(<r>,<s>) and <n> must be coprime at
return r / s mod m;
 called from
QuotientMod( Integers, x![1], y![1], DataType( TypeObj( x ) ) ) called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can replace the integer <n> via 'return <n>;' to continue
brk> quit;
gap> b/a;
ZmodnZObj( 2, 6 )

I'm not sure what the correct behaviour should be here, but
presumably the results should be consistent:  if a congruence
has multiple solutions then either a solution should always be
returned, or fail should always be returned.  I'd guess that
the latter behaviour is more useful and less likely to lead to
hard-to-find bugs, and that divisions by zerodivisors in a ring
should always fail.

I've fixed these bugs in my local copy of GAP.  Is there
some place that I can post or email a patch to, or is that
not useful?

Mark



More information about the Forum mailing list