gcd's of numbers mod N

[Kenneth A. Ribet]

Hi everyone,

If a is an integer mod m (and m is a positive integer), then the gcd of a and m is well defined; it's the gcd of A and m were A is any integer representing a mod m. Consider this transcript in sage:

sage: a = Mod(1,6)
sage: b = Mod(3,6)
sage: print gcd(a-b,6) # is this a bug?
sage: print gcd(b-a,6)
4
2

sage seems to think that the gcd of 6 and (-2 mod 6) is -2 mod 6, which it converts to 4. A mathematician would say that the gcd is 2. Is this a bug, or does sage have a higher purpose here?

Thanks,
Ken

[D. S. McNeil]

> sage seems to think that the gcd of 6 and (-2 mod 6) is -2 mod 6, which it converts to 4.  A mathematician would say that the gcd is 2.
> Is this a bug, or does sage have a higher purpose here?

Sage is actually reasoning slightly differently, I think. First it
decides whether there's a canonical coercion to a common parent. In
this case, it concludes that the common parent should be the ring of
integers modulo 6:

sage: parent(Mod(4,6))
Ring of integers modulo 6
sage: parent(6)
Integer Ring
sage: z = cm.canonical_coercion(Mod(4,6), 6)
sage: z
(4, 0)
sage: parent(z[0]), parent(z[1])
(Ring of integers modulo 6, Ring of integers modulo 6)

There's no gcd method defined in this ring, so it falls back to
attempting to coerce 4 mod 6 and 0 mod 6 to ZZ, which succeeds, and we
get the integer version under which we have

sage: gcd(4,0)
4

It's not clear to me what the best way to handle this case is. Paging
Simon King.. :^)

Doug

[William Stein]

On Sun, Feb 19, 2012 at 8:25 PM, D. S. McNeil <dsm...@gmail.com> wrote:
>> sage seems to think that the gcd of 6 and (-2 mod 6) is -2 mod 6, which it converts to 4.  A mathematician would say that the gcd is 2.
>> Is this a bug, or does sage have a higher purpose here?
>
> Sage is actually reasoning slightly differently, I think.  First it
> decides whether there's a canonical coercion to a common parent.  In
> this case, it concludes that the common parent should be the ring of
> integers modulo 6:
>
> sage: parent(Mod(4,6))
> Ring of integers modulo 6
> sage: parent(6)
> Integer Ring
> sage: z = cm.canonical_coercion(Mod(4,6), 6)
> sage: z
> (4, 0)
> sage: parent(z[0]), parent(z[1])
> (Ring of integers modulo 6, Ring of integers modulo 6)
>
> There's no gcd method defined in this ring,

I think that we should define a gcd method for this ring.

> so it falls back to
> attempting to coerce 4 mod 6 and 0 mod 6 to ZZ, which succeeds, and we
> get the integer version under which we have
>
> sage: gcd(4,0)
> 4
>
> It's not clear to me what the best way to handle this case is.  Paging
> Simon King.. :^)
>
>
> Doug
>

> --
> To post to this group, send email to sage-s...@googlegroups.com
> To unsubscribe from this group, send email to sage-support...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-support
> URL: http://www.sagemath.org

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

[John Cremona]

On 20 February 2012 05:01, William Stein <wst...@gmail.com> wrote:
> On Sun, Feb 19, 2012 at 8:25 PM, D. S. McNeil <dsm...@gmail.com> wrote:
>>> sage seems to think that the gcd of 6 and (-2 mod 6) is -2 mod 6, which it converts to 4.  A mathematician would say that the gcd is 2.
>>> Is this a bug, or does sage have a higher purpose here?
>>
>> Sage is actually reasoning slightly differently, I think.  First it
>> decides whether there's a canonical coercion to a common parent.  In
>> this case, it concludes that the common parent should be the ring of
>> integers modulo 6:
>>
>> sage: parent(Mod(4,6))
>> Ring of integers modulo 6
>> sage: parent(6)
>> Integer Ring
>> sage: z = cm.canonical_coercion(Mod(4,6), 6)
>> sage: z
>> (4, 0)
>> sage: parent(z[0]), parent(z[1])
>> (Ring of integers modulo 6, Ring of integers modulo 6)
>>
>> There's no gcd method defined in this ring,
>
> I think that we should define a gcd method for this ring.

Agreed; after all it is a PID. And easy to define too since
gcd(Mod(a,n),Mod(b,n)) = Mod(gcd(a,b,n),n), where (as Ken will no
doubt be happy about) we can use any lift of a and b; and the output
will always have the form Mod(d,n) where d is a positive divisor of n
(or 0 rather than n itself).

John

[Ken Ribet]

I'll add here is that sage, when asked to find gcd(Mod(5,6),5), will
just echo back 5. Of course it then gives the same answer when asked
to find gcd(Mod(11,6),5). In number theory courses, students are told
that these quantities don't make any sense.

Ken

[William Stein]

I think the optimal answer for gcd(Mod(5,6), 5) would be Mod(1,6), and
the optimal answer for gcd(Mod(11,6), 5) would also be Mod(1,6). In
each case, one applies the canonical coercion map to Z/6Z, then
chooses the smallest representative generator of the ideal generated
by Mod(5,6) and Mod(5,6).

>
> Ken