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)#

Bases: 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 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]