(defn extended-gcd
"Returns a vector containing the [greatest common
divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) and
the [Bézout coefficients](https://en.wikipedia.org/wiki/Bézout%27s_identity)
corresponding to the inputs `a` and `b`.
For more info, see the Wikipedia article on the [Extended Euclidean
algorithm](http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)."
[a b]
(cond (g/zero? a) [(g/abs b) 0 1]
(g/zero? b) [(g/abs a) 1 0]
:else (loop [s 0 s0 1 t 1 t0 0 r (g/abs b) r0 (g/abs a)]
(if (g/zero? r)
[r0 s0 t0]
(let [q (g/quotient r0 r)]
(recur (g/- s0 (g/* q s)) s
(g/- t0 (g/* q t)) t
(g/- r0 (g/* q r)) r))))))