def gcd(a, b)
            if b == 0
                return [a, 1, 0]
            else
                n = (a*1.0/b).floor
                c = a % b
                r = gcd(b, c)
                return [r[0], r[2], r[1]-r[2]*n]
            end
        end
def gcd(a, b)
            if b == 0
                return [a, 1, 0]
            else
                n = (a*1.0/b).floor
                c = a % b
                r = gcd(b, c)
                return [r[0], r[2], r[1]-r[2]*n]
            end
        end
Uses extended Euclidian algorithm to compute the GCD of a pair of
 numbers, and returns [gcd, x, y], such that gcd = ax+ by.

 Note: computing the GCD over a finite field with a = @prime means that
 GCD will always return 1.