# 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[source]#

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]

>>> from sage.all import *
>>> EuclideanDomains()
Category of euclidean domains
>>> EuclideanDomains().super_categories()
[Category of principal ideal domains]

class ElementMethods[source]#

Bases: object

euclidean_degree()[source]#

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

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> x.euclidean_degree()
1
>>> ZZ.one().euclidean_degree()
1

gcd(other)[source]#

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

>>> from sage.all import *
>>> R = PolynomialRing(QQ, sparse=True, names=('x',)); (x,) = R._first_ngens(1)
>>> EuclideanDomains().element_class.gcd(x,x+Integer(1))
-1

quo_rem(other)[source]#

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)

>>> from sage.all import *
>>> R = QQ['x']; (x,) = R._first_ngens(1)
>>> x.quo_rem(x)
(1, 0)

class ParentMethods[source]#

Bases: object

gcd_free_basis(elts)[source]#

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]

>>> from sage.all import *
>>> ZZ.gcd_free_basis([Integer(1)])
[]
>>> ZZ.gcd_free_basis([Integer(4), Integer(30), Integer(14), Integer(49)])
[2, 15, 7]

>>> Pol = QQ['x']; (x,) = Pol._first_ngens(1)
>>> sorted(Pol.gcd_free_basis([
...     (x+Integer(1))**Integer(3)*(x+Integer(2))**Integer(3)*(x+Integer(3)), (x+Integer(1))*(x+Integer(2))*(x+Integer(3)),
...     (x+Integer(1))*(x+Integer(2))*(x+Integer(4))]))
[x + 3, x + 4, x^2 + 3*x + 2]

is_euclidean_domain()[source]#

Return True, since this in an object of the category of Euclidean domains.

EXAMPLES:

sage: Parent(QQ,category=EuclideanDomains()).is_euclidean_domain()
True

>>> from sage.all import *
>>> Parent(QQ,category=EuclideanDomains()).is_euclidean_domain()
True

super_categories()[source]#

EXAMPLES:

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

>>> from sage.all import *
>>> EuclideanDomains().super_categories()
[Category of principal ideal domains]