identification division.
       program-id. gcd.
       author. Bergeretti/Carre.
      *        extended euclids algorithm  
       date-written. January 1985.
       date-compiled.
       data division.
       working-storage section.
       77 a1   pic 9(4).
       77 a2   pic 9(4).
       77 b1   pic 9(4).
       77 b2   pic 9(4).
       77 c    pic 9(4).
       77 d    pic 9(4).
       77 q    pic 9(4).
       77 r    pic 9(4).
       77 out  pic 9(4).       
       linkage section.
       77 m     pic 9(4).
       77 n     pic 9(4).
       77 x     pic 9(4).
       77 y     pic 9(4).
       77 z     pic 9(4).
       procedure division using m, n, x, y, z.
      * m>=0, n>0  
          move 0 to a1
          move 1 to a2
          move 1 to b1
          move 0 to b2
          move m to c
          move n to d
          perform until d = 0
      *      a1 * m + b1 * n = d
      *      a2 * m + b2 * n = c
      *      gcd(c,d) = gcde(m,n)
            compute q = c / d
            compute r = function mod(c, d)
            compute a2 = a2 - q * a1
            compute b2 = b2 - q * b1
            move d to c
            move r to d
            move a1 to r
            move a2 to a1
            move r to a2
            move b1 to r
            move b2 to b1
            move r to b2
          end-perform
          move c to x
          move a2 to y
          move b2 to z
      *    x = gcd(m,n) = y * m + z*n
          compute out=y*m+z*n
          display "x="x" out="out
       end-program gcd.