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)`

and`lcm(F(x),F(y))==lcm(x,y)`

for any x,y in R.

**Note:**See TracTickets for help on using tickets.