EEA := proc(m,u) local s,t,r,q,i;
  # s[0],s[1] := 1,0;
  t[0],t[1] := 0,1;
  r[0],r[1] := m,u;
  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;
u := 72/109 mod m;
EEA(m,u);
u := rand(m)();
EEA(m,u);