Macaulay2 » Documentation
Packages » Macaulay2Doc » elementary arithmetic » gcdCoefficients
next | previous | forward | backward | up | index | toc

gcdCoefficients -- greatest common divisor with coefficients

Description

This returns a sequence of the form (d, r, s), where $d=\gcd(a, b)$ and $r$ and $s$ are the minimal Bézout coefficients satisfying the equation $d = ar + bs$.

It works for integers or elements of polynomial rings in one variable.

i1 : (d, r, s) = gcdCoefficients(46, 240)

o1 = (2, 47, -9)

o1 : Sequence
 
i2 : gcd(46, 240)

o2 = 2
 
i3 : 46 * r + 240 * s

o3 = 2
 
i4 : R = ZZ/2[x]

o4 = R

o4 : PolynomialRing
 
i5 : f = x^8 + x^4 + x^3 + x + 1

      8    4    3
o5 = x  + x  + x  + x + 1

o5 : R
 
i6 : g = x^6 + x^4 + x + 1

      6    4
o6 = x  + x  + x + 1

o6 : R
 
i7 : (d, r, s) = gcdCoefficients(f, g)

          5    4    3    2       7    6    3
o7 = (1, x  + x  + x  + x  + 1, x  + x  + x  + x)

o7 : Sequence
 
i8 : gcd(f, g)

o8 = 1

o8 : R
 
i9 : f * r + g * s

o9 = 1

o9 : R

See also

Ways to use gcdCoefficients:

  • gcdCoefficients(RingElement,RingElement)
  • gcdCoefficients(RingElement,ZZ)
  • gcdCoefficients(ZZ,RingElement)
  • gcdCoefficients(ZZ,ZZ)

For the programmer

The object gcdCoefficients is a method function.

The source of this document is in Macaulay2Doc/doc_arithmetic.m2:149:0.