# function - How do I implement Extended Euclidean algorithm?

How can I implement the Extended Euclidean algorithm? Here's my first attempt:

``(define ex-gcd a b; gcd(a,b) = a * x+ b * y; gcd(a,b)-> always will be 1output: (x.y))``

The algorithm is right here in Wikipedia, you just have to adapt it to only return Bézout coefficients, the `car` part of the returned `cons`-cell will be `x`, and the `cdr` will be `y`:

``````(define (extended-gcd a b)
(let loop ([s 0] [t 1] [r b]
[old-s 1] [old-t 0] [old-r a])
(if (zero? r)
(cons old-s old-t)
(let ((q (quotient old-r r)))
(loop (- old-s (* q s))
(- old-t (* q t))
(- old-r (* q r))
s t r)))))
``````

It's easy to test it using Bézout's identity, use different values for `a` and `b` and verify that it works as advertised:

``````(define (test a b)
(let* ((ans (extended-gcd a b))
(x (car ans))
(y (cdr ans)))
(= (gcd a b) (+ (* a x) (* b y)))))

(test 384 256)
=> #t
``````

Notice that the algorithm calculated other values, by changing what you return you can also obtain the following:

``````Bézout coefficients:     old_s, old_t
Greatest common divisor: old_r
Quotients by the gcd:    t, s
``````