辗转相除法

算法步骤: (Know-How)

1. 设有两个正整数a和b，且a > b。
2. 用a除以b，得到商q和余数r (a = bq + r)。
3. 如果余数r为0，那么b就是a和b的最大公约数。
4. 如果余数r不为0，则将b的值赋给a，将r的值赋给b，然后回到第2步，继续进行运算。[2]

为什么辗转相除法有效？ (Know-Why)

假设我们有两个整数a和b，令 a = bq + r，其中q是商，r是余数。我们的目标是证明 a和b的公约数集合 与 b和r的公约数集合 是完全相同的。如果这两个集合相同，那么它们的最大公约数也必然相同。[4]

证明过程：

1. 证明 a和b的任意公约数，也是b和r的公约数。

   • 假设d是a和b的一个公约数，那么d可以整除a（写作d|a），也可以整除b（写作d|b）。[5]
   • 根据我们的等式 a = bq + r，可以变形为 r = a - bq。[5]
   • 因为d能整除a，也能整除b，所以d也一定能整除 a - bq。[6]
   • 因此，d能整除r。
   • 既然d能整除b，也能整除r，那么d就是b和r的一个公约数。

2. 证明 b和r的任意公约数，也是a和b的公约数。

   • 假设d'是b和r的一个公约数，那么d'可以整除b（d'|b），也可以整除r（d'|r）。
   • 根据我们的等式 a = bq + r。
   • 因为d'能整除b，也能整除r，所以d'也一定能整除 bq + r。
   • 因此，d'能整除a。
   • 既然d'能整除a，也能整除b，那么d'就是a和b的一个公约数。

结论：
通过以上两步，我们证明了a和b的公约数集合与b和r的公约数集合是完全一样的。[4] 因此，它们的最大公约数也必然相等，即 gcd(a, b) = gcd(b, r)。