sage: x,y = R.gens()
sage: f = x*y^2 + 1
sage: gs = [ x*y + 1, y + 1 ]
- sage: multidiv(f, gs)
+ sage: (qs, r) = multidiv(f, gs)
+ sage: (qs, r)
([y, -1], 2)
+ sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
+ True
+ sage: not any( g.lt().divides(m) for m in r.monomials()
+ ....: for g in gs )
+ True
Example 2 in Section 2.3 of Cox, Little, and O'Shea::
sage: x,y = R.gens()
sage: f = x^2*y + x*y^2 + y^2
sage: gs = [ x*y - 1, y^2 - 1 ]
- sage: multidiv(f, gs)
+ sage: (qs, r) = multidiv(f, gs)
+ sage: (qs, r)
([x + y, 1], x + y + 1)
+ sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
+ True
+ sage: not any( g.lt().divides(m) for m in r.monomials()
+ ....: for g in gs )
+ True
+
+ A solution ``g`` to Exercise 6 in Section 2.3 of Cox, Little, and
+ O'Shea that lives in the ideal generated by ``f1`` and ``f2`` but
+ which has nonzero remainder after division::
+
+ sage: R = PolynomialRing(QQ, 'x,y', order='deglex')
+ sage: x,y = R.gens()
+ sage: f1 = 2*x*y^2 - x
+ sage: f2 = 3*x^2*y - y - 1
+ sage: I = R.ideal(f1,f2)
+ sage: g = 2*y*f2
+ sage: g in I
+ True
+ sage: (qs,r) = multidiv(g,[f1,f2])
+ sage: r.is_zero()
+ False
+
+ Two solutions ``g`` to Exercise 7 in Section 2.3 of Cox, Little, and
+ O'Shea that live in the ideal generated by ``f1``, ``f2``, and ``f3``
+ but which have nonzero remainders after division::
+
+ sage: R = PolynomialRing(QQ, 'x,y,z', order='deglex')
+ sage: x,y,z = R.gens()
+ sage: f1 = x^4*y^2 - z
+ sage: f2 = x^3*y^3 - 1
+ sage: f3 = x^2*y^4 - 2*z
+ sage: I = R.ideal(f1,f2,f3)
+ sage: g = x^2*f3
+ sage: g in I
+ True
+ sage: (qs, r) = multidiv(g, [f1,f2,f3])
+ sage: r.is_zero()
+ False
+ sage: g = x*f2
+ sage: g in I
+ True
+ sage: (qs, r) = multidiv(g, [f1,f2,f3])
+ sage: r.is_zero()
+ False
TESTS:
- Derp.
+ If we get a zero remainder, then the numerator should belong to
+ the ideal generated by the denominators::
+
+ sage: set_random_seed()
+ sage: R = PolynomialRing(QQ, 'x,y,z')
+ sage: x,y,z = R.gens()
+ sage: s = ZZ.random_element(1,5).abs()
+ sage: gs = [ R.random_element() for idx in range(s) ]
+ sage: f = R.random_element(ZZ.random_element(10).abs())
+ sage: (qs, r) = multidiv(f,gs)
+ sage: r != 0 or f in R.ideal(gs)
+ True
+
+ The numerator is always the sum of the remainder and the quotients
+ times the denominators, and the remainder's monomials aren't divisible
+ by the leading term of any denominator::
+
+ sage: set_random_seed()
+ sage: R = PolynomialRing(QQ, 'x,y,z')
+ sage: x,y,z = R.gens()
+ sage: s = ZZ.random_element(1,5).abs()
+ sage: gs = [ R.random_element() for idx in range(s) ]
+ sage: f = R.random_element(ZZ.random_element(10).abs())
+ sage: (qs, r) = multidiv(f,gs)
+ sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
+ True
+ sage: r == 0 or (not any( g.lt().divides(m) for m in r.monomials()
+ ....: for g in gs ))
+ True
"""
R = f.parent()
qs = [R.zero()]*s
while p != R.zero():
- for i in range(0,s):
- division_occurred = false
+ i = 0
+ division_occurred = false
+ while i < s:
# If gs[i].lt() divides p.lt(), then this remainder will
# be zero and the quotient will be in R (and not the
# fraction ring, which is important).
qs[i] += factor
p -= factor*gs[i]
division_occurred = true
- break
+ # Don't increment "i" here because we want to try
+ # again with this "denominator" g[i]. We might
+ # get another factor out of it, but we know that
+ # we can't get another factor out of an *earlier*
+ # denominator g[i-k] for some k.
+ else:
+ i += 1
if not division_occurred:
r += p.lt()