1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defun ex-gcd (a b)
(if (= b 0) (values 1 0 a)
(let ((x 0) (y 0) (r 0) (tmp 0))
(multiple-value-bind (x y r) (ex-gcd b (mod a b))
(setf
tmp y
y (- x (* (floor (/ a b)) y))
x tmp)
(values x y r)))))

(let ((x 0) (y 0) (r 0))
(multiple-value-bind (x y r) (ex-gcd 72 98)
(format t "X:~D Y:~D R:~D~%" x y r)
(format t "~D~%" (+ (* 15 72) (* -11 98)))))