Euclid’s coefficients
The following program is based on Euclid’s algorithm and it determines Euclid’s coefficients and of the integers and .
INPUT , (positive integers)
,
,
,
WHILE DO
BEGIN
DIV (integer division)
, ,
, ,
, ,
END
WRITE — The gcd of the numbers and is .
Remark. The values of and produced by the program have the absolute values as close each other as possible (Proof = ?). They differ very often only by 1 when and are two successive prime numbers
, e.g.