# 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 |