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
