# Extended Euclidean Algorithm

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,

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]

• This lacks quite a lot of info. What is the aim of the program? And what is your particular problem? Nov 21, 2019 at 19:56
• The aim of the program is to print out the last elements of lists s & t that would form a solution such that as + by = gcd(a,b). Nov 21, 2019 at 20:25
• Maybe you want double brackets for some of those assignments involving s and t? Nov 22, 2019 at 16:34

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

ClearAll[extendedEuclidean]
extendedEuclidean[a_, b_] :=
First@NestWhile[
{#[], #[] - (Quotient @@ #[[All, 1]]) #[]} &,
{{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 *)