话不多说，进入正题。

欧几里得算法（辗转相除法）

给定两个整数 A 和 B ,求他们两个数的最大公约数。

概念

我先把概念提出，稍后讲原理。

概念:(A,B) = (B,R) R为余数

例：
$(27,33)=?$

解：

33 / 27 = 1 ...... 6  //用较大的数33除以27
27 / 6 = 4 ...... 3   //用原本的除数27作为被除数，余数作为除数
6 / 3 = 2 //除尽

则3是$33$和$27$的最大公约数。

原理

用一个$u$作为$A$和$B$的公约数，则
圈1：$A = a × u$

圈2：$B = b × u$

∵$A$和$B$的余数 $R = A - Bq (q为商)$

∴把圈1和圈2带入，得，

$R = au - b × u × q$

把$u$提出得，

$R = u(a - b × q)$

所以$R$中也含有约数$A$和$B$的约数$u$。

再反过来推，

用一个$v$作为$B$和$R$的公约数，则
圈1：$B = b × v$

圈2：$R = r × v$

∵$A = Bq+R(q为商)$

∴把圈1和圈2带入，得，

$A = b × v × q + r × v$

把$v$提出，得
$A = v(b × q + r)$

所以$A$中也含有$B$和$R$的约数$v$。

所以因为$B$和$R$中的公约数和$A$和$B$中的相等，那么他们的最大公约数也一定相等。

原理部分结束。
收工！