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:

Status badges

Description (last modified by SimonKing)

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) and lcm(F(x),F(y))==lcm(x,y) for any x,y in R.

Change History (1)

comment:1 Changed 11 years ago by SimonKing

  • Description modified (diff)
Note: See TracTickets for help on using tickets.