Code

(define (solve-ax+by=1  a b)
  (if (= b 0)
      (list 1 0)                                     ;; here is the base case
      (let ((q (quotient a b))
	    (r (remainder a b)))
	(let ((recursive-soln (solve-ax+by=1 b r)))
	  (let ((xbar (car recursive-soln))
		(ybar (cadr recursive-soln)))
	    (list ybar                                ;; here is where we use the
		  (- xbar (* q ybar))))))))	      ;; recursion relationships

Let's test it on some basic cases...

(solve-ax+by=1 5 3)
;Value: (2 -3)

(solve-ax+by=1 3 5)
;Value: (-3 2)

(solve-ax+by=1 0 1)
;Value: (0 1)

(solve-ax+by=1 1 0)
;Value: (1 0)

Now let's test it on the example mentioned in the pset...

(define a 1915954701)
;Value: "a --> 1915954701"

(define b 2019374789)
;Value: "b --> 2019374789"

(define answer (solve-ax+by=1 1915954701 2019374789))
;Value: "answer --> (1780184735 -1689014506)"

(+ (* a (car answer))
   (* b (cadr answer)))
;Value: 1

Now let's see if we can verify signatures:

(define signature (sign "Clinton Loves Lewinsky!" my-ks))
;Value: signature

(verify "Clinton Loves Lewinsky!" signature (key-system->public-key my-ks))
;Value: \#t