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_singletonThe 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:
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_degreewas 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 asself
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 ofself.
OUTPUT:
A GCD-free basis (also called a coprime base) of
elts; that is, a set of pairwise relatively prime elements ofselfsuch that any element ofeltscan 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]