#10771: gcd and lcm for fraction fields
--------------------------------+-------------------------------------------
Reporter: SimonKing | Owner: AlexGhitza
Type: PLEASE CHANGE | Status: new
Priority: major | Milestone: sage-4.7
Component: basic arithmetic | Keywords: gcd lcm fraction fields
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Description changed by SimonKing:
Old description:
> At [http://groups.google.com/group/sage-
> devel/browse_thread/thread/cd05585cf395b3a0/a34f04f32d68e525 sage-devel],
> the question was raised whether it really is a good idea that the gcd in
> the rational field should return either `0` or `1`.
>
> Since ''any'' non-zero element of `QQ` qualifies as gcd of two non-zero
> rationals, it should be possible to define gcd and lcm, so that
> `gcd(x,y)*lcm(x,y)==x*y` holds for any rational numbers x,y, and so that
> `gcd(QQ(m),QQ(n))==gcd(m,n)` and `lcm(QQ(m),QQ(n))==lcm(m,n)` for any two
> integers m,n.
>
> Moreover, it should be possible to provide gcd/lcm for any fraction field
> of a `PID`: Note that currently gcd raises a type error for elements of
> `Frac(QQ['x'])`.
>
> The aim is to implement gcd and lcm as `ElementMethods` of the category
> `QuotientFields()`.
>
> It seems that defining `gcd(a/b,c/d) = gcd(a,c)/lcm(b,d)` and
> `lcm(a/b,c/d) = lcm(a,c)/gcd(b,d)` works, ''under the assumption that
> `a/b` and `c/d` are reduced fractions''. Note: Since we need `gcd` for
> `a,b,c,d` anyway, it is no problem to reduce the fractions.
>
> But I am not 100% sure whether that approach is mathematically sober.
New description:
At [http://groups.google.com/group/sage-
devel/browse_thread/thread/cd05585cf395b3a0/a34f04f32d68e525 sage-devel],
the question was raised whether it really is a good idea that the gcd in
the rational field should return either `0` or `1`.
Since ''any'' non-zero element of `QQ` qualifies as gcd of two non-zero
rationals, it should be possible to define gcd and lcm, so that
`gcd(x,y)*lcm(x,y)==x*y` holds for any rational numbers x,y, and so that
`gcd(QQ(m),QQ(n))==gcd(m,n)` and `lcm(QQ(m),QQ(n))==lcm(m,n)` for any two
integers m,n.
Moreover, it should be possible to provide gcd/lcm for any fraction field
of a `PID`: Note that currently gcd raises a type error for elements of
`Frac(QQ['x'])`.
The aim is to implement gcd and lcm as `ElementMethods` of the category
`QuotientFields()`.
'''__Approach__'''
Let R be an integral domain, assume that it provides gcd and lcm, and let
F be its fraction field. Since R has gcd, we can assume that
`x.numerator()` and `x.denominator()` are relatively prime for any element
x of F.
Then, define
{{{
gcd(x,y) =
gcd(x.numerator(),y.numerator())/lcm(x.denominator(),y.denominator())
lcm(x,y) =
lcm(x.numerator(),y.numerator())/gcd(x.denominator(),y.denominator())
}}}
'''__Benefits__'''
If that approach is mathematically sober, we obtain the following
equalities up to units in R:
* `gcd(x,y)*lcm(x,y)==x*y`, for any x,y in F, provided that the equality
holds for any x,y in R.
* `gcd(F(x),F(y))==gcd(x,y)` and `lcm(F(x),F(y))==lcm(x,y)` for any x,y
in R.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10771#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
