extendedgcd[m_, n_, var_] := 
      Module[{x, k, rule, r, q, X}, x[0] = m;  x[1] = n;  k = 0;  
        rule = {};  
        gcdmatrix = {}; 
While[Not[x[k + 1] === 0], 
          k = k + 1; 
r[k] = 
            PolynomialRemainder[x[k - 1], x[k], var]; 
q[
              k] = PolynomialQuotient[x[k - 1], x[k], 
              var]; 
x[k + 1] = 
            r[k]; 
AppendTo[rule, 
            Collect[X[k + 1] -> X[k - 1] - q[k]*X[k] /. rule, {X[0], 
                X[1]}]]; 
AppendTo[
            gcdmatrix, {k, x[k - 1], q[k], x[k], 
              r[k]}];]; 
{x[k], 
          Coefficient[
            X[k - 2] - q[k - 1]*X[k - 1] //. rule, {X[0], X[1]}]}]

{g, {s, t}} = 
      extendedgcd[a = 6  (x^3) + 19  (x^2) + 19  x + 6, 
        b = 6  (x^5) + 13  (x^4) + 12  (x^3) + 13  (x^2) + 6  x, x]

s*a + t*b - g // Expand

gcdmatrix

res = 
      extendedgcd[a = (∑_(k = 0)^5) Random[Integer, {1, 10}] (x^k), 
        b = (∑_(k = 1)^6) Random[Integer, {1, 10}] (x^k), x]

gcdmatrix

Needs["Algebra`PolynomialExtendedGCD`"]

PolynomialExtendedGCD[a, b]