Skip to content

Instantly share code, notes, and snippets.

@jukworks

jukworks/extended-euclid.clj

Created October 16, 2013 08:39
Show Gist options
  • Save jukworks/7004581 to your computer and use it in GitHub Desktop.
Save jukworks/7004581 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment