# 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\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\cdot 523-29\cdot 541.$
Title Euclid’s coefficients EuclidsCoefficients 2013-03-22 15:15:20 2013-03-22 15:15:20 pahio (2872) pahio (2872) 16 pahio (2872) Algorithm msc 11A05 msc 03-04 BezoutsLemma