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]


TESTS:

sage: TestSuite(EuclideanDomains()).run()

class ElementMethods
euclidean_degree()

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 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 [Coh1996].

REFERENCES:

 [Coh1996] Henri Cohen. A Course in Computational Algebraic Number Theory. Springer, 1996.

EXAMPLES:

sage: EuclideanDomains().ElementMethods().gcd(6,4)
2

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

EXAMPLES:

sage: R.<x> = QQ[]
sage: x.quo_rem(x)
(1, 0)

class EuclideanDomains.ParentMethods
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

EuclideanDomains.super_categories()

EXAMPLES:

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


Enumerated Sets

Fields