Opened 11 years ago
Last modified 11 years ago
#10771 closed enhancement
gcd and lcm for fraction fields — at Version 1
Reported by: | SimonKing | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7.2 |
Component: | basic arithmetic | Keywords: | gcd lcm fraction fields |
Cc: | burcin | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
At 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)
andlcm(F(x),F(y))==lcm(x,y)
for any x,y in R.