ExtendedGCD Command
CAS Syntax
- ExtendedGCD( <Integer>,<Integer> )
-
Returns a list containing the integer coefficients \(s, t\) of Bézout’s identity \(as+bt= GCD(a,b)\) and the greatest common divisor of the given integers \(a\) and \(b\). Results are calculated by applying the Extended Euclidean algorithm.
ExtendedGCD(240,46) yields {\(-9,47,2\)}. (Plugging the result into the Bézout’s identity we have: \(-9
\cdot 240+47 \cdot 46=2\)).
- ExtendedGCD( <Polynomial>, <Polynomial> )
-
Returns a list containing the polynomial coefficients \(S(x), T(x)\) of Bézout’s identity for polynomials \(A(x)S(x) + B(x)T(x) = GCD(A(x), B(x))\) and the greatest common divisor of the given polynomials\(A(x)\) and \(B(x)\). Results are calculated by applying the Extended Euclidean algorithm.
ExtendedGCD(x^2-1,x+4) yields {\(1,-x+4,15\)}. (Plugging the result into the Bézout’s identity for polynomials
we have: \(1 \cdot (x^2-1) + (-x+4) \cdot (x+4) = 15\)).
|