2
$\begingroup$

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]
$\endgroup$
3
  • 1
    $\begingroup$ This lacks quite a lot of info. What is the aim of the program? And what is your particular problem? $\endgroup$ Commented Nov 21, 2019 at 19:56
  • $\begingroup$ 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). $\endgroup$
    – Aaronn N
    Commented Nov 21, 2019 at 20:25
  • $\begingroup$ Maybe you want double brackets for some of those assignments involving s and t? $\endgroup$ Commented Nov 22, 2019 at 16:34

1 Answer 1

3
$\begingroup$

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 *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.