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   m0   DO
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
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 valuesMathworldPlanetmathPlanetmathPlanetmath as close each other as possible (Proof = ?).  They differ very often only by 1 when x and y are two successive prime numbersMathworldPlanetmath, e.g.

1= 30523-29541.
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