The following program is based on Euclid's algorithm and it determines Euclid's coefficients $t$ and $d$ of the integers $x$ and $y$

INPUT $x$ $y$     {positive integers}
$m := x$     $n := y$ $b := 0$     $d := 1$ $p := 1$     $t := 0$ WHILE $m \neq 0$ DO
BEGIN
$q := n$ DIV $m$     {integer division}
$h := m$     $m := n-qm$     $n := h$ $h := b$     $b := d-qb$     $d := h$ $h := p$     $p := t-qp$     $t := h$ END
WRITE -- The gcd of the numbers $x$ and $y$ is $n = tx+dy$

Remark. The values of $t$ and $d$ produced by the program have the absolute values as close each other as possible (Proof = ?). They differ very often only by 1 when $x$ and $y$ are two successive prime numbers, e.g. $$1 \,=\, 30\cdot523-29\cdot541.$$