By the way, notice that in http://trac.sagemath.org/sage_trac/ticket/3214 they also added a function "content" which does the old gcd behaviour (i.e. similar to what simon describes).
sage: (1/4).content(1/6) 1/12 On Feb 11, 12:15 pm, koffie <m.derickx.stud...@gmail.com> wrote: > First of all, sorry Simon to have misread you :(. > > To awnser your question. I guess your algorithm makes sense when you > do it with fractions in the reduced form. I will do it only for prime > powers since the general case will follow from this. > Suppose we have two prime powers p^a and p^b with a,b possabilly > negative. Then gcd(p^a,p^b)=p^(min(a,b)) (*) would be sensible and up > to units not depending on any choise. It is easy to see that this > operation is associative and and commutative simply because min(a,b) > has those properties. > Now consider the cases (1) a,b>0, (2) a>0,b<0 (3) a,b<0 (and of course > the more trivial cases with a=0) > In the case (1) we get with your algorithm gcd(p^a,p^b)/ > lcm(1,1)=p^(min(a,b)) which agrees with the definition (*) > In the case (2) a>0 b<0 we get gcd(p^a,1)/lcm(1,p^(-b))=1/(p^(-b))=p^b > which agrees with (*) since b<a > In the case (3) we get gcd(1,1)/lcm(p^(-a),p^(-b))=p^(-max(-a,- > b))=p^min(a,b) which also agrees with (*). > > Kind regards, > Maarten Derickx > > On Feb 11, 11:12 am, Simon King <simon.k...@uni-jena.de> wrote: > > > > > > > > > Hi Tim, > > > I just opened #10771 for that purpose. Algorithm is proposed below. > > > On 11 Feb., 10:55, daly <d...@axiom-developer.org> wrote: > > > > On Fri, 2011-02-11 at 01:49 -0800, Simon King wrote: > > > > Hi, > > > > > On 11 Feb., 09:56, Simon King <simon.k...@uni-jena.de> wrote: > > > > Does anyone have a better idea? Would it be a correct definition if > > > > one insisted on reduced fractions? > > > > That's why I was asking for an algorithm for gcd and lcm > > > in the subdomain. > > > What do you mean by "subdomain"? Do you mean, an integral domain R as > > a subdomain of Frac(R)? > > > > The unit (1) is correct but not by your definition, and > > > apparently not helpful for the original poster. > > > Any unit is a correct answer from the point of view of a PID. That's > > why it makes sense to use the freedom. > > > Here is an algorithm: > > > --------- > > ASSUMPTIONS: > > > R is an integral domain, F is its fraction field. > > gcd and lcm are defined for R > > > INPUT: > > > x,y: Elements of F. > > > Since there is gcd in R, we can assume that x.numerator() and > > y.denominator() are relatively prime, i.e., x=a/b and y=c/d for > > a,b,c,d in R, the two fractions being reduced. > > > OUTPUT: > > > gcd(x,y) returns gcd(x.numerator(),y.numerator())/ > > lcm(x.denominator(),y.denominator()) > > lcm(x,y) returns lcm(x.numerator(),y.numerator())/ > > gcd(x.denominator(),y.denominator()) > > ----------------- > > > PROPERTIES: > > > - Up to units in R, we have gcd(x,y)*lcm(x,y) = gcd(a,c)/ > > lcm(b,d)*lcm(a,c)/gcd(b,d) = a*c/b*d = x*y > > > - Moreover, again up to units in R, we have gcd(a/1,b/1) = gcd(a,b)/ > > lcm(1,1) = gcd(a,b) and lcm(a/1,b/1) = lcm(a,b)/gcd(1,1) = lcm(a,b) > > > My questions to people that get more sleep than I: > > Does that algorithm makes sense, mathematically? > > > At least it seems to me that the gcd-definition is exactly what is > > used in Maxima: > > > sage: P.<x> = QQ[] > > sage: a = (1+x^2)*(1+2*x)^2 > > sage: b = 1-x^4 > > sage: c = (1+3*x^2)*(1+2*x) > > sage: d = 1-x^5 > > sage: x = a/b > > sage: y = c/d > > sage: factor(gcd(maxima(x),maxima(y))) > > (2*x+1)/((x-1)*(x+1)*(x^4+x^3+x^2+x+1)) > > sage: factor(gcd(x.numerator(),y.numerator())/ > > lcm(x.denominator(),y.denominator())) > > (x - 1)^-1 * (x + 1)^-1 * (x + 1/2) * (x^4 + x^3 + x^2 + x + 1)^-1 > > > Best regards, > > Simon -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
