|\^/|     Maple 2022 (X86 64 LINUX)
._|\|   |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple Inc. 2022
 \  MAPLE  /  All rights reserved. Maple is a trademark of
 <____ ____>  Waterloo Maple Inc.
      |       Type ? for help.

> EEA := proc(m,u) local s,t,r,q,i;
>   r[0],r[1] := m,u;
>   # s[0],s[1] := 1,0;
>   t[0],t[1] := 0,1;
>   printf("\n");
>   printf("%4s %10s %10s %10s %12s\n","i","r[i]","t[i]","q[i+1]","r[i]/t[i]");
>   for i from 1 while r[i]<>0 do
>     q[i+1] := iquo(r[i-1],r[i]);
>     r[i+1] := r[i-1]-q[i+1]*r[i];
>     # s[i+1] := s[i-1]-q[i+1]*s[i];
>     t[i+1] := t[i-1]-q[i+1]*t[i];
>     printf("%4d %10d %10d %10d %12a\n",i,r[i],t[i],q[i+1],r[i]/t[i]);
>   od:
> end:

> m := 10^6-17;
                                  m := 999983

> u := 72/109 mod m;
                                  u := 137613

> EEA(m,u);

   i       r[i]       t[i]     q[i+1]    r[i]/t[i]
   1     137613          1          7       137613
   2      36692         -7          3     -36692/7
   3      27537         22          1     27537/22
   4       9155        -29          3     -9155/29
   5         72        109        127       72/109
   6         11     -13872          6    -11/13872
   7          6      83341          1      6/83341
   8          5     -97213          1     -5/97213
   9          1     180554          5     1/180554
> u := rand(m)();
                                  u := 113500

> EEA(m,u);

   i       r[i]       t[i]     q[i+1]    r[i]/t[i]
   1     113500          1          8       113500
   2      91983         -8          1     -91983/8
   3      21517          9          4      21517/9
   4       5915        -44          3     -5915/44
   5       3772        141          1     3772/141
   6       2143       -185          1    -2143/185
   7       1629        326          1     1629/326
   8        514       -511          3     -514/511
   9         87       1859          5      87/1859
  10         79      -9806          1     -79/9806
  11          8      11665          9      8/11665
  12          7    -114791          1    -7/114791
  13          1     126456          7     1/126456
> quit
memory used=1.2MB, alloc=8.3MB, time=0.12