Extended Euclidean algorithm

;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Extended Euclidean algorithm
;; finds gcd(a,b) and solves ax+by=gcd(a,b)
;; returns 3 values: gcd(a,b) x y
;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (egcd a b)
  (let loop ([a a] [b b] [x 0] [y 1] [last-x 1] [last-y 0])
    (if (zero? b)
    (values a last-x last-y)    ; result
    (let ([q (quotient a b)])
      (loop b           ; a
        (remainder a b)     ; b
        (- last-x (* q x))  ; x
        (- last-y (* q y))  ; y
        x               ; last-x
        y)))))                  ; last-y

(define (test-egcd a b)
  (let-values ([(g x y) (egcd a b)])
    (printf "g=~a x=~a y=~a ax+by=~a" g x y (+ (* a x)
                           (* b y)))))