Extended Euclidean Algorithm

Question

I am trying to program the Extended Euclidean Algorithm. Earlier I made some progress past simply generating garbage data. I am supposed to yield two constants s & t that would help compute the constants needed in the Algorithm. However, I cannot compute the right numbers that I need. Here is my function below:

ExtendoEuclid[x_, y_] := 
 Module[{a, b, s = {}, t = {}, q, r, i, sNew, tNew},
  {a, b, i} = {x, y, 2};
  If[b == 0, Return[0],

    s = {1, 0};
    t = {0, 1};

    While[r != 0,

    r = Mod[a, b];
    q = (a - r)/b;

    Print[q];
    Print[r];
    sNew = s[i] - s[i - 1]*q;
    tNew = t[i] - t[i - 1]*q;
    AppendTo[s, sNew];
    AppendTo[t, tNew];

    a = b;
    b = r;
    i++;
    ];

   ];
  Print[Last[s]];
  Print[Last[t]]
  ]






ExtendoEuclid[1873, 19]

Answer 1

Here is a direct implementation of the definition of the Extended Euclidean algorithm from the Wikipedia page:

ClearAll[extendedEuclidean]
extendedEuclidean[a_, b_] :=
 First@NestWhile[
    {#[[2]], #[[1]] - (Quotient @@ #[[All, 1]]) #[[2]]} &,
    {{a, 1, 0}, {b, 0, 1}},
    #[[2, 1]] != 0 &
  ]

extendedEuclidean[a, b] returns a list of three numbers, the first being the GCD of $a$ and $b$, and the second two being the Bézout coefficients $s$ and $t$, such that:

$$\text{gcd(}{a,b}) =a\ s+b\ t$$

Trying the example on the wiki page:

extendedEuclidean[240, 46]
(* Out: {2, -9, 47} *)

And checking the properties mentioned above:

GCD[240, 46] == First @ extendedEuclidean[240, 46]              (* True *)
GCD[240, 46] == {240, 46}.extendedEuclidean[240, 46][[2;;]]     (* True *)