Opened 11 years ago

Closed 9 years ago

# Add a default gcd and lcm methods for fields

Reported by: Owned by: lftabera AlexGhitza major sage-duplicate/invalid/wontfix algebra lcm, gcd, fields Marco Streng N/A

This ticket should be closed as fixed by #10771

For the case of field elements gcd and lcm methods are not of great interest. However, they can be addecuated for some reasons.

• Some algorithms may accept as input either polynomials or rational functions. In these algorithms we may reduce a list of polynomials and rational functions to a common denominator. If all the inputs are polynomials, the denominators are the one element of the base field. In this case, lcm would fail.

See #9063 for a case of this problem.

• Rational numbers already have custom gcd and lcm methods.

-It would erase the following problem. Currently, if we are dealing with elements in a finite field, the gcd of the elements can be computed sometimes coercing to the integers and doing computations. This lead to inconsistencies.

```sage: a=F(2)
sage: gcd(a,a)
2
sage: gcd(a,p)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/luisfe/Varios/Comprobantes-gastos/<ipython console> in <module>()

/opt/SAGE/sage-4.5.2/local/lib/python2.6/site-packages/sage/rings/arith.pyc in gcd(a, b, **kwargs)
1423                 return ZZ(a).gcd(ZZ(b))
1424             except TypeError:
-> 1425                 raise TypeError, "unable to find gcd of %s and %s"%(a,b)
1426
1427     from sage.structure.sequence import Sequence

TypeError: unable to find gcd of 2 and p
```

I propose the following:

• For gcd, follow the convention of the rational cesa. If both elements are 0, return 0 (on the appropriate field). Otherwise return 1
• For lcm, if one of the elements is zero, return zero. Otherwise return 1.

#9063 depends on this bug to be merged.

### comment:1 Changed 11 years ago by lftabera

• Milestone set to sage-4.5.3

### comment:2 Changed 11 years ago by lftabera

To make thing worse, currently (sage 4.5.3.alpha2) GF(5)(4) is an IntegerMod_int that does not derive from FieldElement? but CommutativeRingElement?

### comment:3 follow-up: ↓ 4 Changed 10 years ago by mstreng

related ticket with different proposal: #10771

### comment:4 in reply to: ↑ 3 Changed 10 years ago by SimonKing

related ticket with different proposal: #10771

I wouldn't say that it is a different proposal. #10771 treats the case of fields that happen to be the fraction field of a unique factorization domain. In this case, one can do better than to return either 0 or 1.

However, #10771 does not consider the case of fields that are no fraction fields, or are fraction fields of rings that do not provide lcm and gcd. I suggest that for that purpose, one should implement gcd and lcd as element methods of the category of `Fields()`. That would also solve the problem that `IntegerMod_int` does not derive from `FieldElement`.

### comment:5 Changed 9 years ago by mstreng

• Milestone changed from sage-4.8 to sage-duplicate/invalid/wontfix

Is everything on this ticket fixed already? It seems that #10771 did implement `Fields.ElementMethods.gcd()` after all and its behaviour is as requested in this ticket.

### comment:6 Changed 9 years ago by mstreng

• Status changed from new to needs_info

### comment:7 Changed 9 years ago by lftabera

• Status changed from needs_info to needs_review

Yes, this ticket should be resolved as duplicated.

### comment:8 Changed 9 years ago by mstreng

• Description modified (diff)
• Status changed from needs_review to positive_review

### comment:9 Changed 9 years ago by mstreng

• Authors Luis Felipe Taberea deleted

### comment:10 Changed 9 years ago by jdemeyer

• Resolution set to duplicate
• Reviewers set to Marco Streng
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.