Euclid’s coefficients

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\ne 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=\mathrm{\hspace{0.17em}30}\cdot 523-29\cdot 541.$$

Title	Euclid’s coefficients
Canonical name	EuclidsCoefficients
Date of creation	2013-03-22 15:15:20
Last modified on	2013-03-22 15:15:20
Owner	pahio (2872)
Last modified by	pahio (2872)
Numerical id	16
Author	pahio (2872)
Entry type	Algorithm
Classification	msc 11A05
Classification	msc 03-04
Related topic	BezoutsLemma