Dense univariate polynomials over \(\ZZ\), implemented using FLINT¶

AUTHORS:

David Harvey: rewrote to talk to NTL directly, instead of via ntl.pyx (2007-09); a lot of this was based on Joel Mohler’s recent rewrite of the NTL wrapper
David Harvey: split off from polynomial_element_generic.py (2007-09)
Burcin Erocal: rewrote to use FLINT (2008-06-16)

class sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint[source]¶

Bases: Polynomial

A dense polynomial over the integers, implemented via FLINT.

_add_(right)[source]¶

Return self plus right.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: f = 2*x + 1
sage: g = -3*x^2 + 6
sage: f + g
-3*x^2 + 2*x + 7

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = Integer(2)*x + Integer(1)
>>> g = -Integer(3)*x**Integer(2) + Integer(6)
>>> f + g
-3*x^2 + 2*x + 7

_sub_(right)[source]¶

Return self minus right.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: f = 2*x + 1
sage: g = -3*x^2 + 6
sage: f - g
3*x^2 + 2*x - 5

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = Integer(2)*x + Integer(1)
>>> g = -Integer(3)*x**Integer(2) + Integer(6)
>>> f - g
3*x^2 + 2*x - 5

_lmul_(right)[source]¶

Return self multiplied by right, where right is a scalar (integer).

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: x*3
3*x
sage: (2*x^2 + 4)*3
6*x^2 + 12

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> x*Integer(3)
3*x
>>> (Integer(2)*x**Integer(2) + Integer(4))*Integer(3)
6*x^2 + 12

_rmul_(right)[source]¶

Return self multiplied by right, where right is a scalar (integer).

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: 3*x
3*x
sage: 3*(2*x^2 + 4)
6*x^2 + 12

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> Integer(3)*x
3*x
>>> Integer(3)*(Integer(2)*x**Integer(2) + Integer(4))
6*x^2 + 12

_mul_(right)[source]¶

Return self multiplied by right.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: (x - 2)*(x^2 - 8*x + 16)
x^3 - 10*x^2 + 32*x - 32

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> (x - Integer(2))*(x**Integer(2) - Integer(8)*x + Integer(16))
x^3 - 10*x^2 + 32*x - 32

_mul_trunc_(right, n)[source]¶

Truncated multiplication.

See also

_mul_() for standard multiplication

EXAMPLES:

Sage

sage: x = polygen(ZZ)
sage: p1 = 1 + x + x^2 + x^4
sage: p2 = -2 + 3*x^2 + 5*x^4
sage: p1._mul_trunc_(p2, 4)
3*x^3 + x^2 - 2*x - 2
sage: (p1*p2).truncate(4)
3*x^3 + x^2 - 2*x - 2
sage: p1._mul_trunc_(p2, 6)
5*x^5 + 6*x^4 + 3*x^3 + x^2 - 2*x - 2

Python

>>> from sage.all import *
>>> x = polygen(ZZ)
>>> p1 = Integer(1) + x + x**Integer(2) + x**Integer(4)
>>> p2 = -Integer(2) + Integer(3)*x**Integer(2) + Integer(5)*x**Integer(4)
>>> p1._mul_trunc_(p2, Integer(4))
3*x^3 + x^2 - 2*x - 2
>>> (p1*p2).truncate(Integer(4))
3*x^3 + x^2 - 2*x - 2
>>> p1._mul_trunc_(p2, Integer(6))
5*x^5 + 6*x^4 + 3*x^3 + x^2 - 2*x - 2

content()[source]¶

Return the greatest common divisor of the coefficients of this polynomial. The sign is the sign of the leading coefficient. The content of the zero polynomial is zero.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: (2*x^2 - 4*x^4 + 14*x^7).content()
2
sage: x.content()
1
sage: R(1).content()
1
sage: R(0).content()
0

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> (Integer(2)*x**Integer(2) - Integer(4)*x**Integer(4) + Integer(14)*x**Integer(7)).content()
2
>>> x.content()
1
>>> R(Integer(1)).content()
1
>>> R(Integer(0)).content()
0

degree(gen=None)[source]¶

Return the degree of this polynomial.

The zero polynomial has degree \(-1\).

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: x.degree()
1
sage: (x^2).degree()
2
sage: R(1).degree()
0
sage: R(0).degree()
-1

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> x.degree()
1
>>> (x**Integer(2)).degree()
2
>>> R(Integer(1)).degree()
0
>>> R(Integer(0)).degree()
-1

disc(proof=True)[source]¶

Return the discriminant of self, which is by definition

\[(-1)^{m(m-1)/2} \mathop{\mathrm{resultant}}(a, a')/\mathop{\mathrm{lc}}(a),\]

where \(m = \mathop{\mathrm{deg}}(a)\), and \(\mathop{\mathrm{lc}}(a)\) is the leading coefficient of a. If proof is False (the default is True), then this function may use a randomized strategy that errors with probability no more than \(2^{-80}\).

EXAMPLES:

Sage

sage: R.<x> = ZZ[]
sage: f = 3*x^3 + 2*x + 1
sage: f.discriminant()
-339
sage: f.discriminant(proof=False)
-339

Python

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(3)*x**Integer(3) + Integer(2)*x + Integer(1)
>>> f.discriminant()
-339
>>> f.discriminant(proof=False)
-339

discriminant(proof=True)[source]¶

Return the discriminant of self, which is by definition

\[(-1)^{m(m-1)/2} \mathop{\mathrm{resultant}}(a, a')/\mathop{\mathrm{lc}}(a),\]

EXAMPLES:

Sage

sage: R.<x> = ZZ[]
sage: f = 3*x^3 + 2*x + 1
sage: f.discriminant()
-339
sage: f.discriminant(proof=False)
-339

Python

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = Integer(3)*x**Integer(3) + Integer(2)*x + Integer(1)
>>> f.discriminant()
-339
>>> f.discriminant(proof=False)
-339

factor()[source]¶

This function overrides the generic polynomial factorization to make a somewhat intelligent decision to use PARI or NTL based on some benchmarking.

Note: This function factors the content of the polynomial, which can take very long if it’s a really big integer. If you do not need the content factored, divide it out of your polynomial before calling this function.

EXAMPLES:

Sage

sage: R.<x> = ZZ[]
sage: f = x^4 - 1
sage: f.factor()
(x - 1) * (x + 1) * (x^2 + 1)
sage: f = 1 - x
sage: f.factor()
(-1) * (x - 1)
sage: f.factor().unit()
-1
sage: f = -30*x; f.factor()
(-1) * 2 * 3 * 5 * x

Python

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(4) - Integer(1)
>>> f.factor()
(x - 1) * (x + 1) * (x^2 + 1)
>>> f = Integer(1) - x
>>> f.factor()
(-1) * (x - 1)
>>> f.factor().unit()
-1
>>> f = -Integer(30)*x; f.factor()
(-1) * 2 * 3 * 5 * x

factor_mod(p)[source]¶

Return the factorization of self modulo the prime \(p\).

INPUT:

p – prime

OUTPUT: factorization of self reduced modulo \(p\)

EXAMPLES:

Sage

sage: R.<x> = ZZ['x']
sage: f = -3*x*(x-2)*(x-9) + x
sage: f.factor_mod(3)
x
sage: f = -3 * x * (x - 2) * (x - 9)
sage: f.factor_mod(3)
Traceback (most recent call last):
...
ArithmeticError: factorization of 0 is not defined

sage: f = 2 * x * (x - 2) * (x - 9)
sage: f.factor_mod(7)
(2) * x * (x + 5)^2

Python

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = -Integer(3)*x*(x-Integer(2))*(x-Integer(9)) + x
>>> f.factor_mod(Integer(3))
x
>>> f = -Integer(3) * x * (x - Integer(2)) * (x - Integer(9))
>>> f.factor_mod(Integer(3))
Traceback (most recent call last):
...
ArithmeticError: factorization of 0 is not defined

>>> f = Integer(2) * x * (x - Integer(2)) * (x - Integer(9))
>>> f.factor_mod(Integer(7))
(2) * x * (x + 5)^2

factor_padic(p, prec=10)[source]¶

Return \(p\)-adic factorization of self to given precision.

INPUT:

p – prime
prec – integer; the precision

OUTPUT: factorization of self over the completion at \(p\)

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: f = x^2 + 1
sage: f.factor_padic(5, 4)
((1 + O(5^4))*x + 2 + 5 + 2*5^2 + 5^3 + O(5^4))
* ((1 + O(5^4))*x + 3 + 3*5 + 2*5^2 + 3*5^3 + O(5^4))

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(2) + Integer(1)
>>> f.factor_padic(Integer(5), Integer(4))
((1 + O(5^4))*x + 2 + 5 + 2*5^2 + 5^3 + O(5^4))
* ((1 + O(5^4))*x + 3 + 3*5 + 2*5^2 + 3*5^3 + O(5^4))

A more difficult example:

Sage

sage: f = 100 * (5*x + 1)^2 * (x + 5)^2
sage: f.factor_padic(5, 10)
(4 + O(5^10)) * (5 + O(5^11))^2 * ((1 + O(5^10))*x + 5 + O(5^10))^2
* ((5 + O(5^10))*x + 1 + O(5^10))^2

Python

>>> from sage.all import *
>>> f = Integer(100) * (Integer(5)*x + Integer(1))**Integer(2) * (x + Integer(5))**Integer(2)
>>> f.factor_padic(Integer(5), Integer(10))
(4 + O(5^10)) * (5 + O(5^11))^2 * ((1 + O(5^10))*x + 5 + O(5^10))^2
* ((5 + O(5^10))*x + 1 + O(5^10))^2

gcd(right)[source]¶

Return the GCD of self and right. The leading coefficient need not be 1.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: f = (6*x + 47) * (7*x^2 - 2*x + 38)
sage: g = (6*x + 47) * (3*x^3 + 2*x + 1)
sage: f.gcd(g)
6*x + 47

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = (Integer(6)*x + Integer(47)) * (Integer(7)*x**Integer(2) - Integer(2)*x + Integer(38))
>>> g = (Integer(6)*x + Integer(47)) * (Integer(3)*x**Integer(3) + Integer(2)*x + Integer(1))
>>> f.gcd(g)
6*x + 47

inverse_series_trunc(prec)[source]¶

Return a polynomial approximation of precision prec of the inverse series of this polynomial.

EXAMPLES:

Sage

sage: x = polygen(ZZ)
sage: p = 1 + x + 2*x^2
sage: q5 = p.inverse_series_trunc(5)
sage: q5
-x^4 + 3*x^3 - x^2 - x + 1
sage: p*q5
-2*x^6 + 5*x^5 + 1

sage: (x-1).inverse_series_trunc(5)
-x^4 - x^3 - x^2 - x - 1

sage: q100 = p.inverse_series_trunc(100)
sage: (q100 * p).truncate(100)
1

Python

>>> from sage.all import *
>>> x = polygen(ZZ)
>>> p = Integer(1) + x + Integer(2)*x**Integer(2)
>>> q5 = p.inverse_series_trunc(Integer(5))
>>> q5
-x^4 + 3*x^3 - x^2 - x + 1
>>> p*q5
-2*x^6 + 5*x^5 + 1

>>> (x-Integer(1)).inverse_series_trunc(Integer(5))
-x^4 - x^3 - x^2 - x - 1

>>> q100 = p.inverse_series_trunc(Integer(100))
>>> (q100 * p).truncate(Integer(100))
1

is_one()[source]¶

Return True if self is equal to one.

EXAMPLES:

Sage

sage: R.<x> = ZZ[]
sage: R(0).is_one()
False
sage: R(1).is_one()
True
sage: x.is_one()
False

Python

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> R(Integer(0)).is_one()
False
>>> R(Integer(1)).is_one()
True
>>> x.is_one()
False

is_zero()[source]¶

Return True if self is equal to zero.

EXAMPLES:

Sage

sage: R.<x> = ZZ[]
sage: R(0).is_zero()
True
sage: R(1).is_zero()
False
sage: x.is_zero()
False

Python

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> R(Integer(0)).is_zero()
True
>>> R(Integer(1)).is_zero()
False
>>> x.is_zero()
False

lcm(right)[source]¶

Return the LCM of self and right.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: f = (6*x + 47) * (7*x^2 - 2*x + 38)
sage: g = (6*x + 47) * (3*x^3 + 2*x + 1)
sage: h = f.lcm(g); h
126*x^6 + 951*x^5 + 486*x^4 + 6034*x^3 + 585*x^2 + 3706*x + 1786
sage: h == (6*x + 47) * (7*x^2 - 2*x + 38) * (3*x^3 + 2*x + 1)
True

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = (Integer(6)*x + Integer(47)) * (Integer(7)*x**Integer(2) - Integer(2)*x + Integer(38))
>>> g = (Integer(6)*x + Integer(47)) * (Integer(3)*x**Integer(3) + Integer(2)*x + Integer(1))
>>> h = f.lcm(g); h
126*x^6 + 951*x^5 + 486*x^4 + 6034*x^3 + 585*x^2 + 3706*x + 1786
>>> h == (Integer(6)*x + Integer(47)) * (Integer(7)*x**Integer(2) - Integer(2)*x + Integer(38)) * (Integer(3)*x**Integer(3) + Integer(2)*x + Integer(1))
True

list(copy=True)[source]¶

Return a new copy of the list of the underlying elements of self.

EXAMPLES:

Sage

sage: x = PolynomialRing(ZZ,'x').0
sage: f = x^3 + 3*x - 17
sage: f.list()
[-17, 3, 0, 1]
sage: f = PolynomialRing(ZZ,'x')(0)
sage: f.list()
[]

Python

>>> from sage.all import *
>>> x = PolynomialRing(ZZ,'x').gen(0)
>>> f = x**Integer(3) + Integer(3)*x - Integer(17)
>>> f.list()
[-17, 3, 0, 1]
>>> f = PolynomialRing(ZZ,'x')(Integer(0))
>>> f.list()
[]

pseudo_divrem(B)[source]¶

Write A = self. This function computes polynomials \(Q\) and \(R\) and an integer \(d\) such that

\[\mathop{\mathrm{lead}}(B)^d A = B Q + R\]

where R has degree less than that of B.

INPUT:

B – a polynomial over \(\ZZ\)

OUTPUT:

Q, R – polynomials
d – nonnegative integer

EXAMPLES:

Sage

sage: R.<x> = ZZ['x']
sage: A = R(range(10))
sage: B = 3*R([-1, 0, 1])
sage: Q, R, d = A.pseudo_divrem(B)
sage: Q, R, d
(9*x^7 + 8*x^6 + 16*x^5 + 14*x^4 + 21*x^3 + 18*x^2 + 24*x + 20, 75*x + 60, 1)
sage: B.leading_coefficient()^d * A == B*Q + R
True

Python

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> A = R(range(Integer(10)))
>>> B = Integer(3)*R([-Integer(1), Integer(0), Integer(1)])
>>> Q, R, d = A.pseudo_divrem(B)
>>> Q, R, d
(9*x^7 + 8*x^6 + 16*x^5 + 14*x^4 + 21*x^3 + 18*x^2 + 24*x + 20, 75*x + 60, 1)
>>> B.leading_coefficient()**d * A == B*Q + R
True

quo_rem(right)[source]¶

Attempts to divide self by right, and return a quotient and remainder.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: f = R(range(10)); g = R([-1, 0, 1])
sage: q, r = f.quo_rem(g)
sage: q, r
(9*x^7 + 8*x^6 + 16*x^5 + 14*x^4 + 21*x^3 + 18*x^2 + 24*x + 20, 25*x + 20)
sage: q*g + r == f
True

sage: f = x^2
sage: f.quo_rem(0)
Traceback (most recent call last):
...
ZeroDivisionError: division by zero polynomial

sage: f = (x^2 + 3) * (2*x - 1)
sage: f.quo_rem(2*x - 1)
(x^2 + 3, 0)

sage: f = x^2
sage: f.quo_rem(2*x - 1)
(0, x^2)

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = R(range(Integer(10))); g = R([-Integer(1), Integer(0), Integer(1)])
>>> q, r = f.quo_rem(g)
>>> q, r
(9*x^7 + 8*x^6 + 16*x^5 + 14*x^4 + 21*x^3 + 18*x^2 + 24*x + 20, 25*x + 20)
>>> q*g + r == f
True

>>> f = x**Integer(2)
>>> f.quo_rem(Integer(0))
Traceback (most recent call last):
...
ZeroDivisionError: division by zero polynomial

>>> f = (x**Integer(2) + Integer(3)) * (Integer(2)*x - Integer(1))
>>> f.quo_rem(Integer(2)*x - Integer(1))
(x^2 + 3, 0)

>>> f = x**Integer(2)
>>> f.quo_rem(Integer(2)*x - Integer(1))
(0, x^2)

real_root_intervals()[source]¶

Return isolating intervals for the real roots of this polynomial.

EXAMPLES: We compute the roots of the characteristic polynomial of some Salem numbers:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: f = 1 - x^2 - x^3 - x^4 + x^6
sage: f.real_root_intervals()                                               # needs sage.libs.linbox
[((1/2, 3/4), 1), ((1, 3/2), 1)]

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> f = Integer(1) - x**Integer(2) - x**Integer(3) - x**Integer(4) + x**Integer(6)
>>> f.real_root_intervals()                                               # needs sage.libs.linbox
[((1/2, 3/4), 1), ((1, 3/2), 1)]

resultant(other, proof=True)[source]¶

Return the resultant of self and other, which must lie in the same polynomial ring.

If proof=False (the default is proof=True), then this function may use a randomized strategy that errors with probability no more than \(2^{-80}\).

INPUT:

other – a polynomial

OUTPUT: an element of the base ring of the polynomial ring

EXAMPLES:

Sage

sage: x = PolynomialRing(ZZ,'x').0
sage: f = x^3 + x + 1;  g = x^3 - x - 1
sage: r = f.resultant(g); r
-8
sage: r.parent() is ZZ
True

Python

>>> from sage.all import *
>>> x = PolynomialRing(ZZ,'x').gen(0)
>>> f = x**Integer(3) + x + Integer(1);  g = x**Integer(3) - x - Integer(1)
>>> r = f.resultant(g); r
-8
>>> r.parent() is ZZ
True

reverse(degree=None)[source]¶

Return a polynomial with the coefficients of this polynomial reversed.

If an optional degree argument is given the coefficient list will be truncated or zero padded as necessary before computing the reverse.

EXAMPLES:

Sage

sage: R.<x> = ZZ[]
sage: p = R([1,2,3,4]); p
4*x^3 + 3*x^2 + 2*x + 1
sage: p.reverse()
x^3 + 2*x^2 + 3*x + 4
sage: p.reverse(degree=6)
x^6 + 2*x^5 + 3*x^4 + 4*x^3
sage: p.reverse(degree=2)
x^2 + 2*x + 3

Python

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> p = R([Integer(1),Integer(2),Integer(3),Integer(4)]); p
4*x^3 + 3*x^2 + 2*x + 1
>>> p.reverse()
x^3 + 2*x^2 + 3*x + 4
>>> p.reverse(degree=Integer(6))
x^6 + 2*x^5 + 3*x^4 + 4*x^3
>>> p.reverse(degree=Integer(2))
x^2 + 2*x + 3

revert_series(n)[source]¶

Return a polynomial \(f\) such that \(f(\) self \((x)) =\) self \((f(x)) = x\) (mod \(x^n\)).

EXAMPLES:

Sage

sage: R.<t> = ZZ[]
sage: f = t - t^3 + t^5
sage: f.revert_series(6)
2*t^5 + t^3 + t

sage: f.revert_series(-1)
Traceback (most recent call last):
...
ValueError: argument n must be a nonnegative integer, got -1

sage: g = - t^3 + t^5
sage: g.revert_series(6)
Traceback (most recent call last):
...
ValueError: self must have constant coefficient 0 and a unit for coefficient t^1

Python

>>> from sage.all import *
>>> R = ZZ['t']; (t,) = R._first_ngens(1)
>>> f = t - t**Integer(3) + t**Integer(5)
>>> f.revert_series(Integer(6))
2*t^5 + t^3 + t

>>> f.revert_series(-Integer(1))
Traceback (most recent call last):
...
ValueError: argument n must be a nonnegative integer, got -1

>>> g = - t**Integer(3) + t**Integer(5)
>>> g.revert_series(Integer(6))
Traceback (most recent call last):
...
ValueError: self must have constant coefficient 0 and a unit for coefficient t^1

squarefree_decomposition()[source]¶

Return the square-free decomposition of self. This is a partial factorization of self into square-free, relatively prime polynomials.

This is a wrapper for the NTL function SquareFreeDecomp.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ)
sage: p = (x-1)^2 * (x-2)^2 * (x-3)^3 * (x-4)
sage: p.squarefree_decomposition()
(x - 4) * (x^2 - 3*x + 2)^2 * (x - 3)^3
sage: p = 37 * (x-1)^2 * (x-2)^2 * (x-3)^3 * (x-4)
sage: p.squarefree_decomposition()
(37) * (x - 4) * (x^2 - 3*x + 2)^2 * (x - 3)^3

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> p = (x-Integer(1))**Integer(2) * (x-Integer(2))**Integer(2) * (x-Integer(3))**Integer(3) * (x-Integer(4))
>>> p.squarefree_decomposition()
(x - 4) * (x^2 - 3*x + 2)^2 * (x - 3)^3
>>> p = Integer(37) * (x-Integer(1))**Integer(2) * (x-Integer(2))**Integer(2) * (x-Integer(3))**Integer(3) * (x-Integer(4))
>>> p.squarefree_decomposition()
(37) * (x - 4) * (x^2 - 3*x + 2)^2 * (x - 3)^3

xgcd(right)[source]¶

Return a triple \((g,s,t)\) such that \(g = s\cdot{}\) self + \(t\cdot{}\) right and such that \(g\) is the gcd of self and right up to a divisor of the resultant of self and other.

As integer polynomials do not form a principal ideal domain, it is not always possible given \(a\) and \(b\) to find a pair \(s,t\) such that \(gcd(a,b) = sa + tb\). Take \(a=x+2\) and \(b=x+4\) as an example for which the gcd is \(1\) but the best you can achieve in the Bezout identity is \(2\).

If self and right are coprime as polynomials over the rationals, then g is guaranteed to be the resultant of self and right, as a constant polynomial.

EXAMPLES:

Sage

sage: P.<x> = PolynomialRing(ZZ)

sage: (x + 2).xgcd(x + 4)
(2, -1, 1)
sage: (x + 2).resultant(x + 4)
2
sage: (x + 2).gcd(x + 4)
1

sage: F = (x^2 + 2)*x^3; G = (x^2 + 2) * (x - 3)
sage: g, u, v = F.xgcd(G)
sage: g, u, v
(27*x^2 + 54, 1, -x^2 - 3*x - 9)
sage: u*F + v*G
27*x^2 + 54

sage: zero = P(0)
sage: x.xgcd(zero)
(x, 1, 0)
sage: zero.xgcd(x)
(x, 0, 1)

sage: F = (x - 3)^3; G = (x - 15)^2
sage: g, u, v = F.xgcd(G)
sage: g, u, v
(2985984, -432*x + 8208, 432*x^2 + 864*x + 14256)
sage: u*F + v*G
2985984

Python

>>> from sage.all import *
>>> P = PolynomialRing(ZZ, names=('x',)); (x,) = P._first_ngens(1)

>>> (x + Integer(2)).xgcd(x + Integer(4))
(2, -1, 1)
>>> (x + Integer(2)).resultant(x + Integer(4))
2
>>> (x + Integer(2)).gcd(x + Integer(4))
1

>>> F = (x**Integer(2) + Integer(2))*x**Integer(3); G = (x**Integer(2) + Integer(2)) * (x - Integer(3))
>>> g, u, v = F.xgcd(G)
>>> g, u, v
(27*x^2 + 54, 1, -x^2 - 3*x - 9)
>>> u*F + v*G
27*x^2 + 54

>>> zero = P(Integer(0))
>>> x.xgcd(zero)
(x, 1, 0)
>>> zero.xgcd(x)
(x, 0, 1)

>>> F = (x - Integer(3))**Integer(3); G = (x - Integer(15))**Integer(2)
>>> g, u, v = F.xgcd(G)
>>> g, u, v
(2985984, -432*x + 8208, 432*x^2 + 864*x + 14256)
>>> u*F + v*G
2985984