Univariate polynomials over \(\QQ\) implemented via FLINT

AUTHOR:

  • Sebastian Pancratz
class sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint

Bases: sage.rings.polynomial.polynomial_element.Polynomial

Univariate polynomials over the rationals, implemented via FLINT.

Internally, we represent rational polynomial as the quotient of an integer polynomial and a positive denominator which is coprime to the content of the numerator.

TESTS:

sage: f = QQ['x'].random_element()
sage: from sage.rings.polynomial.polynomial_rational_flint import Polynomial_rational_flint
sage: isinstance(f, Polynomial_rational_flint)
True
_add_(right)

Returns the sum of two rational polynomials.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = 2/3 + t + 2*t^3
sage: g = -1 + t/3 - 10/11*t^4
sage: f + g
-10/11*t^4 + 2*t^3 + 4/3*t - 1/3

TESTS:

sage: R.<t> = QQ[]
sage: f = R.random_element(2000)
sage: f + f == 2 * f              # indirect doctest
True
_sub_(right)

Returns the difference of two rational polynomials.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = -10/11*t^4 + 2*t^3 + 4/3*t - 1/3
sage: g = 2*t^3
sage: f - g                                 # indirect doctest
-10/11*t^4 + 4/3*t - 1/3

TESTS:

sage: R.<t> = QQ[]
sage: f = R.random_element(2000)
sage: f - f/2 == 1/2 * f          # indirect doctest
True
_lmul_(right)

Returns self * right, where right is a rational number.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = 3/2*t^3 - t + 1/3
sage: f * 6                   # indirect doctest
9*t^3 - 6*t + 2
_rmul_(left)

Returns left * self, where left is a rational number.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = 3/2*t^3 - t + 1/3
sage: 6 * f                  # indirect doctest
9*t^3 - 6*t + 2
_mul_(right)

Returns the product of self and right.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = -1 + 3*t/2 - t^3
sage: g = 2/3 + 7/3*t + 3*t^2
sage: f * g                           # indirect doctest
-3*t^5 - 7/3*t^4 + 23/6*t^3 + 1/2*t^2 - 4/3*t - 2/3

TESTS:

sage: R.<t> = QQ[]
sage: f = R.random_element(2000)
sage: g = R.random_element(2000)
sage: (f + g) * (f - g) == f^2 - g^2  # indirect doctest
True
_mul_trunc_(right, n)

Truncated multiplication.

EXAMPLES:

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

sage: p1._mul_trunc_(p2, 1)
0
sage: p1._mul_trunc_(p2, 0)
Traceback (most recent call last):
...
ValueError: n must be > 0

ALGORITHM:

Call the FLINT method fmpq_poly_mullow.

degree()

Return the degree of self.

By convention, the degree of the zero polynomial is -1.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = 1 + t + t^2/2 + t^3/3 + t^4/4
sage: f.degree()
4
sage: g = R(0)
sage: g.degree()
-1

TESTS:

sage: type(f.degree())
<type 'sage.rings.integer.Integer'>
denominator()

Returns the denominator of self.

EXAMPLE:

sage: R.<t> = QQ[]
sage: f = (3 * t^3 + 1) / -3
sage: f.denominator()
3
disc()

Returns the discriminant of this polynomial.

The discriminant \(R_n\) is defined as

\[R_n = a_n^{2 n-2} \prod_{1 \le i < j \le n} (r_i - r_j)^2,\]

where \(n\) is the degree of this polynomial, \(a_n\) is the leading coefficient and the roots over \(\QQbar\) are \(r_1, \ldots, r_n\).

The discriminant of constant polynomials is defined to be 0.

OUTPUT:

  • Discriminant, an element of the base ring of the polynomial ring

Note

Note the identity \(R_n(f) := (-1)^(n (n-1)/2) R(f,f') a_n^(n-k-2)\), where \(n\) is the degree of this polynomial, \(a_n\) is the leading coefficient, \(f'\) is the derivative of \(f\), and \(k\) is the degree of \(f'\). Calls resultant().

ALGORITHM:

Use PARI.

EXAMPLES:

In the case of elliptic curves in special form, the discriminant is easy to calculate:

sage: R.<t> = QQ[]
sage: f = t^3 + t + 1
sage: d = f.discriminant(); d
-31
sage: d.parent() is QQ
True
sage: EllipticCurve([1, 1]).discriminant() / 16
-31
sage: R.<t> = QQ[]
sage: f = 2*t^3 + t + 1
sage: d = f.discriminant(); d
-116
sage: R.<t> = QQ[]
sage: f = t^3 + 3*t - 17
sage: f.discriminant()
-7911

TESTS:

sage: R.<t> = QQ[]
sage: R(0).discriminant()
0
sage: R(2/3).discriminant()
0
sage: (t + 1/2).discriminant()
1

Variable names that are reserved in PARI, such as I, are supported (see trac ticket #20631):

sage: R.<I> = QQ[]
sage: (I^2 + 1).discriminant()
-4
discriminant()

Returns the discriminant of this polynomial.

The discriminant \(R_n\) is defined as

\[R_n = a_n^{2 n-2} \prod_{1 \le i < j \le n} (r_i - r_j)^2,\]

where \(n\) is the degree of this polynomial, \(a_n\) is the leading coefficient and the roots over \(\QQbar\) are \(r_1, \ldots, r_n\).

The discriminant of constant polynomials is defined to be 0.

OUTPUT:

  • Discriminant, an element of the base ring of the polynomial ring

Note

Note the identity \(R_n(f) := (-1)^(n (n-1)/2) R(f,f') a_n^(n-k-2)\), where \(n\) is the degree of this polynomial, \(a_n\) is the leading coefficient, \(f'\) is the derivative of \(f\), and \(k\) is the degree of \(f'\). Calls resultant().

ALGORITHM:

Use PARI.

EXAMPLES:

In the case of elliptic curves in special form, the discriminant is easy to calculate:

sage: R.<t> = QQ[]
sage: f = t^3 + t + 1
sage: d = f.discriminant(); d
-31
sage: d.parent() is QQ
True
sage: EllipticCurve([1, 1]).discriminant() / 16
-31
sage: R.<t> = QQ[]
sage: f = 2*t^3 + t + 1
sage: d = f.discriminant(); d
-116
sage: R.<t> = QQ[]
sage: f = t^3 + 3*t - 17
sage: f.discriminant()
-7911

TESTS:

sage: R.<t> = QQ[]
sage: R(0).discriminant()
0
sage: R(2/3).discriminant()
0
sage: (t + 1/2).discriminant()
1

Variable names that are reserved in PARI, such as I, are supported (see trac ticket #20631):

sage: R.<I> = QQ[]
sage: (I^2 + 1).discriminant()
-4
factor_mod(p)

Returns the factorization of self modulo the prime p.

Assumes that the degree of this polynomial is at least one, and raises a ValueError otherwise.

INPUT:

  • p - Prime number

OUTPUT:

  • Factorization of this polynomial modulo p

EXAMPLES:

sage: R.<x> = QQ[]
sage: (x^5 + 17*x^3 + x+ 3).factor_mod(3)
x * (x^2 + 1)^2
sage: (x^5 + 2).factor_mod(5)
(x + 2)^5

Variable names that are reserved in PARI, such as zeta, are supported (see trac ticket #20631):

sage: R.<zeta> = QQ[]
sage: (zeta^2 + zeta + 1).factor_mod(7)
(zeta + 3) * (zeta + 5)
factor_padic(p, prec=10)

Return the \(p\)-adic factorization of this polynomial to the given precision.

INPUT:

  • p - Prime number
  • prec - Integer; the precision

OUTPUT:

  • factorization of self viewed as a \(p\)-adic polynomial

EXAMPLES:

sage: R.<x> = QQ[]
sage: f = x^3 - 2
sage: f.factor_padic(2)
(1 + O(2^10))*x^3 + (O(2^10))*x^2 + (O(2^10))*x + (2 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + 2^9 + O(2^10))
sage: f.factor_padic(3)
(1 + O(3^10))*x^3 + (O(3^10))*x^2 + (O(3^10))*x + (1 + 2*3 + 2*3^2 + 2*3^3 + 2*3^4 + 2*3^5 + 2*3^6 + 2*3^7 + 2*3^8 + 2*3^9 + O(3^10))
sage: f.factor_padic(5)
((1 + O(5^10))*x + (2 + 4*5 + 2*5^2 + 2*5^3 + 5^4 + 3*5^5 + 4*5^7 + 2*5^8 + 5^9 + O(5^10))) * ((1 + O(5^10))*x^2 + (3 + 2*5^2 + 2*5^3 + 3*5^4 + 5^5 + 4*5^6 + 2*5^8 + 3*5^9 + O(5^10))*x + (4 + 5 + 2*5^2 + 4*5^3 + 4*5^4 + 3*5^5 + 3*5^6 + 4*5^7 + 4*5^9 + O(5^10)))

The input polynomial is considered to have “infinite” precision, therefore the \(p\)-adic factorization of the polynomial is not the same as first coercing to \(Q_p\) and then factoring (see also trac ticket #15422):

sage: f = x^2 - 3^6
sage: f.factor_padic(3,5)
((1 + O(3^5))*x + (3^3 + O(3^5))) * ((1 + O(3^5))*x + (2*3^3 + 2*3^4 + O(3^5)))
sage: f.change_ring(Qp(3,5)).factor()
Traceback (most recent call last):
...
PrecisionError: p-adic factorization not well-defined since the discriminant is zero up to the requestion p-adic precision

A more difficult example:

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

Try some bogus inputs:

sage: f.factor_padic(3,-1)
Traceback (most recent call last):
...
ValueError: prec_cap must be non-negative.
sage: f.factor_padic(6,10)
Traceback (most recent call last):
...
ValueError: p must be prime
sage: f.factor_padic('hello', 'world')
Traceback (most recent call last):
...
TypeError: unable to convert 'hello' to an integer
galois_group(pari_group=False, algorithm='pari')

Returns the Galois group of self as a permutation group.

INPUT:

  • self - Irreducible polynomial
  • pari_group - bool (default: False); if True instead return the Galois group as a PARI group. This has a useful label in it, and may be slightly faster since it doesn’t require looking up a group in Gap. To get a permutation group from a PARI group P, type PermutationGroup(P).
  • algorithm - 'pari', 'kash', 'magma' (default: 'pari', except when the degree is at least 12 in which case 'kash' is tried).

OUTPUT:

  • Galois group

ALGORITHM:

The Galois group is computed using PARI in C library mode, or possibly KASH or MAGMA.

Note

The PARI documentation contains the following warning: The method used is that of resolvent polynomials and is sensitive to the current precision. The precision is updated internally but, in very rare cases, a wrong result may be returned if the initial precision was not sufficient.

MAGMA does not return a provably correct result. Please see the MAGMA documentation for how to obtain a provably correct result.

EXAMPLES:

sage: R.<x> = QQ[]
sage: f = x^4 - 17*x^3 - 2*x + 1
sage: G = f.galois_group(); G            # optional - database_gap
Transitive group number 5 of degree 4
sage: G.gens()                           # optional - database_gap
[(1,2), (1,2,3,4)]
sage: G.order()                          # optional - database_gap
24

It is potentially useful to instead obtain the corresponding PARI group, which is little more than a 4-tuple. See the PARI manual for the exact details. (Note that the third entry in the tuple is in the new standard ordering.)

sage: f = x^4 - 17*x^3 - 2*x + 1
sage: G = f.galois_group(pari_group=True); G
PARI group [24, -1, 5, "S4"] of degree 4
sage: PermutationGroup(G)                # optional - database_gap
Transitive group number 5 of degree 4

You can use KASH to compute Galois groups as well. The advantage is that KASH can compute Galois groups of fields up to degree 21, whereas PARI only goes to degree 11. (In my not-so-thorough experiments PARI is faster than KASH.)

sage: f = x^4 - 17*x^3 - 2*x + 1
sage: f.galois_group(algorithm='kash')   # optional - kash
Transitive group number 5 of degree 4

sage: f = x^4 - 17*x^3 - 2*x + 1
sage: f.galois_group(algorithm='magma')  # optional - magma database_gap
Transitive group number 5 of degree 4

TESTS:

We illustrate the behaviour in the case of reducible polynomials:

sage: R.<t> = QQ[]
sage: f = (1 + t)^2
sage: f.galois_group()
Traceback (most recent call last):
...
ValueError: The polynomial must be irreducible

Variable names that are reserved in PARI, such as zeta, are supported (see trac ticket #20631):

sage: R.<zeta> = QQ[]
sage: (zeta^2 + zeta + 1).galois_group(pari_group=True)
PARI group [2, -1, 1, "S2"] of degree 2
gcd(right)

Returns the (monic) greatest common divisor of self and right.

Corner cases: if self and right are both zero, returns zero. If only one of them is zero, returns the other polynomial, up to normalisation.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = -2 + 3*t/2 + 4*t^2/7 - t^3
sage: g = 1/2 + 4*t + 2*t^4/3
sage: f.gcd(g)
1
sage: f = (-3*t + 1/2) * f
sage: g = (-3*t + 1/2) * (4*t^2/3 - 1) * g
sage: f.gcd(g)
t - 1/6
hensel_lift(p, e)

Assuming that this polynomial factors modulo \(p\) into distinct monic factors, computes the Hensel lifts of these factors modulo \(p^e\). We assume that self has integer coefficients.

Returns an empty list if this polynomial has degree less than one.

INPUT:

  • p - Prime number; coerceable to Integer
  • e - Exponent; coerceable to Integer

OUTPUT:

  • Hensel lifts; list of polynomials over \(\ZZ / p^e \ZZ\)

EXAMPLES:

sage: R.<x> = QQ[]
sage: R((x-1)*(x+1)).hensel_lift(7, 2)
[x + 1, x + 48]

If the input polynomial \(f\) is not monic, we get a factorization of \(f / lc(f)\):

sage: R(2*x^2 - 2).hensel_lift(7, 2)
[x + 1, x + 48]

TESTS:

sage: R.<x> = QQ[]
sage: R(0).hensel_lift(7, 2)
[]
sage: R(x).hensel_lift(7, 2)
[x]
sage: R(x-1).hensel_lift(7, 2)
[x + 48]

Variable names that are reserved in PARI, such as I, are supported (see trac ticket #20631):

sage: R.<I> = QQ[]
sage: (I^2 + 1).hensel_lift(5, 3)
[I + 57, I + 68]
sage: (I^2 + 1).hensel_lift(2, 3)
Traceback (most recent call last):
...
ValueError: I^2 + 1 is not square-free modulo 2
inverse_series_trunc(prec)

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

EXAMPLES:

sage: x = polygen(QQ)
sage: p = 2 + x - 3/5*x**2
sage: q5 = p.inverse_series_trunc(5)
sage: q5
151/800*x^4 - 17/80*x^3 + 11/40*x^2 - 1/4*x + 1/2
sage: q5 * p
-453/4000*x^6 + 253/800*x^5 + 1

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

TESTS:

sage: (0*x).inverse_series_trunc(4)
Traceback (most recent call last):
...
ValueError: constant term is zero
sage: x.inverse_series_trunc(4)
Traceback (most recent call last):
...
ValueError: constant term is zero
sage: (x+1).inverse_series_trunc(0)
Traceback (most recent call last):
...
ValueError: the precision must be positive, got 0
is_irreducible()

Returns whether self is irreducible.

This method computes the primitive part as an element of \(\ZZ[t]\) and calls the method is_irreducible for elements of that polynomial ring.

By definition, over any integral domain, an element \(r\) is irreducible if and only if it is non-zero, not a unit and whenever \(r = ab\) then \(a\) or \(b\) is a unit.

OUTPUT:

  • bool - Whether this polynomial is irreducible

EXAMPLES:

sage: R.<t> = QQ[]
sage: (t^2 + 2).is_irreducible()
True
sage: (t^2 - 1).is_irreducible()
False

TESTS:

sage: R.<t> = QQ[]
sage: R(0).is_irreducible()
False
sage: R(-1/2).is_irreducible()
False
sage: (t+1).is_irreducible()
True
is_one()

Returns whether or not this polynomial is one.

EXAMPLES:

sage: R.<x> = QQ[]
sage: R([0,1]).is_one()
False
sage: R([1]).is_one()
True
sage: R([0]).is_one()
False
sage: R([-1]).is_one()
False
sage: R([1,1]).is_one()
False
is_zero()

Returns whether or not self is the zero polynomial.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = 1 - t + 1/2*t^2 - 1/3*t^3
sage: f.is_zero()
False
sage: R(0).is_zero()
True
lcm(right)

Returns the monic (or zero) least common multiple of self and right.

Corner cases: if either of self and right are zero, returns zero. This behaviour is ensures that the relation lcm(a,b) gcd(a,b) == a b holds up to multiplication by rationals.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = -2 + 3*t/2 + 4*t^2/7 - t^3
sage: g = 1/2 + 4*t + 2*t^4/3
sage: f.lcm(g)
t^7 - 4/7*t^6 - 3/2*t^5 + 8*t^4 - 75/28*t^3 - 66/7*t^2 + 87/8*t + 3/2
sage: f.lcm(g) * f.gcd(g) // (f * g)
-3/2
list()

Returns a list with the coefficients of self.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = 1 + t + t^2/2 + t^3/3 + t^4/4
sage: f.list()
[1, 1, 1/2, 1/3, 1/4]
sage: g = R(0)
sage: g.list()
[]
numerator()

Returns the numerator of self.

Representing self as the quotient of an integer polynomial and a positive integer denominator (coprime to the content of the polynomial), returns the integer polynomial.

EXAMPLE:

sage: R.<t> = QQ[]
sage: f = (3 * t^3 + 1) / -3
sage: f.numerator()
-3*t^3 - 1
quo_rem(right)

Returns the quotient and remainder of the Euclidean division of self and right.

Raises a ZerodivisionError if right is zero.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = R.random_element(2000)
sage: g = R.random_element(1000)
sage: q, r = f.quo_rem(g)
sage: f == q*g + r
True
real_root_intervals()

Returns isolating intervals for the real roots of self.

EXAMPLES:

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

sage: R.<t> = QQ[]
sage: f = 1 - t^2 - t^3 - t^4 + t^6
sage: f.real_root_intervals()
[((1/2, 3/4), 1), ((1, 3/2), 1)]
resultant(right)

Returns the resultant of self and right.

Enumerating the roots over \(\QQ\) as \(r_1, \cdots, r_m\) and \(s_1, \cdots, s_n\) and letting \(x\) and \(y\) denote the leading coefficients of \(f\) and \(g\), the resultant of the two polynomials is defined by

\[x^{\deg g} y^{\deg f} \prod_{i,j} (r_i - s_j).\]

Corner cases: if one of the polynomials is zero, the resultant is zero. Note that otherwise if one of the polynomials is constant, the last term in the above is the empty product.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = (t - 2/3) * (t + 4/5) * (t - 1)
sage: g = (t - 1/3) * (t + 1/2) * (t + 1)
sage: f.resultant(g)
119/1350
sage: h = (t - 1/3) * (t + 1/2) * (t - 1)
sage: f.resultant(h)
0
reverse(degree=None)

Reverse the coefficients of this polynomial (thought of as a polynomial of degree degree).

INPUT:

  • degree (None or integral value that fits in an unsigned long, default: degree of self) - if specified, truncate or zero pad the list of coefficients to this degree before reversing it.

EXAMPLES:

We first consider the simplest case, where we reverse all coefficients of a polynomial and obtain a polynomial of the same degree:

sage: R.<t> = QQ[]
sage: f = 1 + t + t^2 / 2 + t^3 / 3 + t^4 / 4
sage: f.reverse()
t^4 + t^3 + 1/2*t^2 + 1/3*t + 1/4

Next, an example we the returned polynomial has lower degree because the original polynomial has low coefficients equal to zero:

sage: R.<t> = QQ[]
sage: f = 3/4*t^2 + 6*t^7
sage: f.reverse()
3/4*t^5 + 6

The next example illustrates the passing of a value for degree less than the length of self, notationally resulting in truncation prior to reversing:

sage: R.<t> = QQ[]
sage: f = 1 + t + t^2 / 2 + t^3 / 3 + t^4 / 4
sage: f.reverse(2)
t^2 + t + 1/2

Now we illustrate the passing of a value for degree greater than the length of self, notationally resulting in zero padding at the top end prior to reversing:

sage: R.<t> = QQ[]
sage: f = 1 + t + t^2 / 2 + t^3 / 3
sage: f.reverse(4)
t^4 + t^3 + 1/2*t^2 + 1/3*t

TESTS:

We illustrate two ways in which the interpretation of degree as an unsigned long int may fail. Firstly, an integral value which is too large, yielding an OverflowError:

sage: R.<t> = QQ[]
sage: f = 1 + t/2
sage: f.reverse(2**64 - 1)
Traceback (most recent call last):
...
OverflowError: long int too large to convert

Secondly, a value which cannot be converted to an integral value, resulting in a ValueError:

sage: R.<t> = QQ[]
sage: f = 1 + t/2
sage: f.reverse(I)
Traceback (most recent call last):
...
ValueError: cannot convert I + 1 to int

We check that this specialized implementation is compatible with the generic one:

sage: all((t + 2*t^2).reverse(degree=d)
....:     == Polynomial.reverse(t + 2*t^2, degree=d)
....:     for d in [None, 0, 1, 2, 3, 4, 5])
True
revert_series(n)

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

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = t - t^3/6 + t^5/120
sage: f.revert_series(6)
3/40*t^5 + 1/6*t^3 + t

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

sage: g = - t^3/3 + t^5/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
truncate(n)

Returns self truncated modulo \(t^n\).

INPUT:

  • n - The power of \(t\) modulo which self is truncated

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = 1 - t + 1/2*t^2 - 1/3*t^3
sage: f.truncate(0)
0
sage: f.truncate(2)
-t + 1
xgcd(right)

Returns polynomials d, s, and t such that d == s * self + t * right, where d is the (monic) greatest common divisor of self and right. The choice of s and t is not specified any further.

Corner cases: if self and right are zero, returns zero polynomials. Otherwise, if only self is zero, returns (d, s, t) = (right, 0, 1) up to normalisation, and similarly if only right is zero.

EXAMPLES:

sage: R.<t> = QQ[]
sage: f = 2/3 + 3/4 * t - t^2
sage: g = -3 + 1/7 * t
sage: f.xgcd(g)
(1, -12/5095, -84/5095*t - 1701/5095)

TESTS:

The following example used to crash (cf. trac ticket #11771):

sage: R.<t> = QQ[]
sage: f = 10**383 * (t+1)
sage: g = 10**445 * t^2 + 1
sage: r = f.xgcd(g)
sage: r[0] == f.gcd(g)
True
sage: r[1]*f + r[2]*g == r[0]
True