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]

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]

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

EuclideanDomains()
EuclideanDomains().super_categories()
class ElementMethods[source]

Bases: object

euclidean_degree()[source]

Return the degree of this element as an element of a 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 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

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

R.<x> = QQ[]
x.euclidean_degree()
ZZ.one().euclidean_degree()
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

R.<x> = PolynomialRing(QQ, sparse=True)
EuclideanDomains().element_class.gcd(x,x+1)
quo_rem(other)[source]

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)

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

R.<x> = QQ[]
x.quo_rem(x)
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]

ZZ.gcd_free_basis([1])
ZZ.gcd_free_basis([4, 30, 14, 49])
Pol.<x> = QQ[]
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)]))
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

Parent(QQ,category=EuclideanDomains()).is_euclidean_domain()
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]

EuclideanDomains().super_categories()