Euclidean domains¶
AUTHORS:
Teresa GomezDiaz (2008): initial version
Julian Rueth (20130913): added euclidean degree, quotient remainder, and their tests

class
sage.categories.euclidean_domains.
EuclideanDomains
(s=None)¶ Bases:
sage.categories.category_singleton.Category_singleton
The category of constructive euclidean domains, i.e., one can divide producing a quotient and a remainder where the remainder is either zero or its
ElementMethods.euclidean_degree()
is smaller than the divisor.EXAMPLES:
sage: EuclideanDomains() Category of euclidean domains sage: EuclideanDomains().super_categories() [Category of principal ideal domains]

class
ElementMethods
¶ Bases:
object

euclidean_degree
()¶ Return the degree of this element as an element of an Euclidean domain, i.e., for elements \(a\), \(b\) the euclidean degree \(f\) satisfies the usual properties:
if \(b\) is not zero, then there are elements \(q\) and \(r\) such that \(a = bq + r\) with \(r = 0\) or \(f(r) < f(b)\)
if \(a,b\) are not zero, then \(f(a) \leq f(ab)\)
Note
The name
euclidean_degree
was chosen because the euclidean function has different names in different contexts, e.g., absolute value for integers, degree for polynomials.OUTPUT:
For nonzero elements, a natural number. For the zero element, this might raise an exception or produce some other output, depending on the implementation.
EXAMPLES:
sage: R.<x> = QQ[] sage: x.euclidean_degree() 1 sage: ZZ.one().euclidean_degree() 1

gcd
(other)¶ Return the greatest common divisor of this element and
other
.INPUT:
other
– an element in the same ring asself
ALGORITHM:
Algorithm 3.2.1 in [Coh1993].
EXAMPLES:
sage: R.<x> = PolynomialRing(QQ, sparse=True) sage: EuclideanDomains().element_class.gcd(x,x+1) 1

quo_rem
(other)¶ Return the quotient and remainder of the division of this element by the nonzero element
other
.INPUT:
other
– an element in the same euclidean domain
OUTPUT:
a pair of elements
EXAMPLES:
sage: R.<x> = QQ[] sage: x.quo_rem(x) (1, 0)


class
ParentMethods
¶ Bases:
object

gcd_free_basis
(elts)¶ Compute a set of coprime elements that can be used to express the elements of
elts
.INPUT:
elts
 A sequence of elements ofself
.
OUTPUT:
A GCDfree basis (also called a coprime base) of
elts
; that is, a set of pairwise relatively prime elements ofself
such that any element ofelts
can be written as a product of elements of the set.ALGORITHM:
Naive implementation of the algorithm described in Section 4.8 of Bach & Shallit [BS1996].
EXAMPLES:
sage: ZZ.gcd_free_basis([1]) [] sage: ZZ.gcd_free_basis([4, 30, 14, 49]) [2, 15, 7] sage: Pol.<x> = QQ[] sage: sorted(Pol.gcd_free_basis([ ....: (x+1)^3*(x+2)^3*(x+3), (x+1)*(x+2)*(x+3), ....: (x+1)*(x+2)*(x+4)])) [x + 3, x + 4, x^2 + 3*x + 2]

is_euclidean_domain
()¶ Return True, since this in an object of the category of Euclidean domains.
EXAMPLES:
sage: Parent(QQ,category=EuclideanDomains()).is_euclidean_domain() True


super_categories
()¶ EXAMPLES:
sage: EuclideanDomains().super_categories() [Category of principal ideal domains]

class