Euclidean algorithm

《初等数论》 · 第 7 页

(1) 式所指出的计算方法，叫作辗转相除法。

由 admin 提交

《LECTURE NOTES IN ANALYSIS (2011)》 · 第 11 页 · Section 1.2「Divisibility」，Theorem 1.11

The Euclidean algorithm. Given integers $b$ and $c>0$, we make a repeated application of the division algorithm, Theorem 1.2, to obtain a series of equations. The greatest common divisor $(b,c)$ of $b$ and $c$ is $r_j$, the last nonzero remainder in the division process. Values of $x_0$ and $y_0$ in $(b,c)=bx_0+cy_0$ can be obtained by writing each $r_i$ as a linear combination of $b$ and $c$.