# Euclidean domains¶

AUTHORS:

• Teresa Gomez-Diaz (2008): initial version
• Julian Rueth (2013-09-13): added euclidean degree, quotient remainder, and their tests
class sage.categories.euclidean_domains.EuclideanDomains(s=None)

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:

1. 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)$$
2. 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 non-zero 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 as self

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 non-zero 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 of self.

OUTPUT:

A GCD-free basis (also called a coprime base) of elts; that is, a set of pairwise relatively prime elements of self such that any element of elts 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]