extended-euclid.clj

(defn extended-euclid [m n]
  (loop [ap 1
         a  0
         bp 0
         b  1
         c  m
         d  n]
    (let [q (int (/ c d))
          r (mod c d)]
      (if (zero? r)
        [a b]
        (recur a (- ap (* q a)) b (- bp (* q b)) d r)))))

;; (extended-euclid 551 1769) => [-16 5]
;; (+ (* -16 551) (* 5 1769)) => 29