[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