On Feb 11, 4:25 am, koffie <m.derickx.stud...@gmail.com> wrote: > By the way, notice that inhttp://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 >
Which agrees with what I have suggested before - gcd "analog" for fields should have some other name. After all, since any rational number is divisible by any non-zero, how can we pick "the greatest" of them all? For ZZ the notion of greatness agrees with the usual understanding of greater... How about such an approach: 1) if gcd got elements of a fraction field, e.g. (2/1, 4), it tries to convert them to the ring of intergers and compute the gcd there (and lcm too) 2) if it fails, raise an exception This will take care of the original problem. Thank you, Andrey > 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
