輾轉相除法

在數學中，辗转相除法，又称欧几里得算法（英語：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

辗转相除法的演示动画：
两条线段長分别可表示252和105，則其中每一小分段長代表最大公因數21。如动画所示，只要輾轉地从大数中减去小数，直到其中一段的长度为0，此时剩下的一条线段的长度就是252和105的最大公因数。

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。例如，252和105的最大公约数是21（${\displaystyle 252=21\times 12;105=21\times 5}$）；因为${\displaystyle 252-105=21\times (12-5)=147}$，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数为零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如${\displaystyle 21=5\times 105+(-2)\times 252}$。这个重要的結論叫做貝祖定理。

辗转相除法最早出现在欧几里得的《几何原本》中（大约公元前300年），所以它是现行的算法中歷史最悠久的。这个算法原先只用来处理自然数和几何长度（相當於正實數），但在19世纪，辗转相除法被推广至其他类型的數學對象，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。

辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。^[1]在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。

辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的五倍。拉梅于1844年证明了这点，同時這也標誌著计算复杂性理论的開端。

背景

最大公约数

欧几里得的辗转相除法计算的是两个自然数$a$ 和$b$ 的最大公约数$g$ ，意思是能够同时整除$a$ 和$b$ 的自然数中最大的一个。两个数的最大公约数通常写成${\displaystyle \gcd(a,b)}$ ，或者简写成$(a,b)$ ^[2]，但是第二种写法也被使用在其他数学概念，如二维向量的坐标。

如果${\displaystyle \gcd(a,b)=1}$ ，則稱$a$ 和$b$ 互素。^[3]a和b是否互素和它们是否素数无关。^[4]如，6和35都不是素数，因为它们都可以分解为多于一个素因数的乘积：6 = 2 × 3，35 = 5 × 7。但是，6和35互素，因为除了1以外没有自然数同时整除6和35。

 

一个24×60的长方形正好被十个12×12的方格填满，其中12是24和60的最大公约数。一般地，当且仅当$c$ 是$a$ 和$b$ 的公约数时，${\displaystyle a\times b}$ 尺寸的长方形可被边长c的正方形正好填满。

令${\displaystyle g=\gcd(a,b)}$ 。由于$a$ 和$b$ 都是$g$ 的整数倍，所以可以写成${\displaystyle a=mg,b=ng}$ ，并且不存在更大的整数${\displaystyle G>g}$ 使等式成立。为了使$g$ 尽可能大，就要使$a$ 和$b$ 中所有公约数都提取出来归入$g$ 中，所以自然数$m$ 和$n$ 一定互素，并且$a$ 和$b$ 的最大公约数$g$ 可以被$a$ 和$b$ 的所有其他公因数$c$ 整除。^[5]

我们可以用右图来解释最大公约数的概念：^[6]設一个长方形的边长为$a$ 和$b$ 。因为$a$ 和$b$ 的任何公约数$c$ 都可以整除$a$ 和$b$ ，所以长方形的边都可以等分为长度为$c$ 的线段，也就是长方形可以被边长为$c$ 的正方形正好填满。而最大公约数$g$ 是所有可能的$c$ 中最大的一个。例如，一个24 × 60的长方形区域可以分成1 × 1、2 × 2、3 × 3、6 × 6或12 × 12的正方形网格。也就是说，12是24和60的最大公约数。

$a$ 和$b$ 的最大公约数是两数共有的素因数的乘积。^[7]例如，462可以分解成2 × 3 × 7 × 11；1071可以分解成3 × 3 × 7 × 17。462和1071的最大公约数等于它们共有的素因数的乘积3 × 7 = 21。如果两数没有公共的素因数，那么它们的最大公约数是1，也即这两个数互素。辗转相除法的优点就在於它能以有系統的方式求出兩數的最大公约数，而無需分別對它們作因式分解。^[8][9]大数的素因数分解被認為是一個困難的問題，即使是现代的计算机也非常难於處理，所以许多加密系统的原理都是建基於此。^[10]

在数学中，尤其是抽象代数的环论中，最大公约数有一个更加巧妙的定义：^[11]$a$ 和$b$ 的最大公约数$g$ 是^[11]$a$ 和$b$ 的线性和中的最小正整數，即所有形如${\displaystyle ua+vb}$ （其中$u$ 和$v$ 是整数）的数中的最小正整数。可以證明，所有${\displaystyle ua+vb}$ 都是$g$ 的整数倍（${\displaystyle ua+vb=mg}$ ，其中$m$ 是整数）。用现代数学语言來說，$a$ 和$b$ 生成的理想即是由$g$ 生成的主理想。最大公约数的这个定义和其他定义的等价性将在下面描述。

三个数的最大公约数的定义和两个数的相同，即是它们共有的素因数的积^[12]，它们或者也可以按下式计算^[13]：

${\displaystyle \gcd(a,b,c)=\gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c)=\gcd(\gcd(a,c),b).}$ 

所以，欧几里得的辗转相除法实际可以计算任意多整数的最大公约数。

归纳、递归和无穷递降

下文的論證會用到三種相關的数学方法，分別是数学归纳法、递归和无穷递降。数学归纳法^[14]经常用来证明某個定理對所有自然数成立：^[15]首先证明定理对一个特定的数$n_{0}$ 成立（通常是1）；然后證明如果定理对自然数$n$ 成立的話，那麼它对自然数$n+1$ 成立。這樣，便可證明定理对所有大于$n_{0}$ 的自然数也成立。递归^[16]是将相关的数组成一个数列（${\displaystyle a_{1},a_{2},a_{3},\cdots }$ ），^[17]當中除初始項外，其中每一项都用前一项或前几项表示。如斐波那契数列就是递归的，每一项$F_{n}$ 都等于${\displaystyle F_{n-1}+F_{n-2}}$ （${\displaystyle n\geqq 2}$ ）。辗转相除法中的一些等式也是递归的。最后，无穷递降^[18]是用方程的一个自然数解导出比它小的自然数解。^[19]但是，这种转化不能永远进行下去，因为只有有限個小於原來的自然数解的自然数。所以，要麼方程無解，不然在有限步内必然能得出最小的自然數解。在下文會用到此法來证明辗转相除法一定会在有限步内结束。

算法描述

计算过程

辗转相除法是一种递归算法，每一步计算的输出值就是下一步计算时的输入值。^[20]设$k$ 表示步骤数（从0开始计数），算法的计算过程如下。

每一步的输入是都是前两次计算的非負余数$r_{k-1}$ 和${\displaystyle r_{k-2}}$ 。因为每一步计算出的余数都在不断减小，所以，$r_{k-1}$ 小于${\displaystyle r_{k-2}}$ 。在第$k$ 步中，算法计算出满足以下等式的商$q_{k}$ 和余数$r_{k}$ ：

${\displaystyle r_{k-2}=q_{k}r_{k-1}+r_{k}}$ 

其中${\displaystyle 0\leq r_{k}<r_{k-1}}$ 。也就是${\displaystyle r_{k-2}}$ 要不断减去$r_{k-1}$ 直到比$r_{k-1}$ 小。

為求簡明，以下只說明如何求兩個非負整數$a$ 和$b$ 的最大公約數（負數的情況是簡單的）。在第一步计算时（$k=0$ ），设${\displaystyle r_{-2}}$ 和${\displaystyle r_{-1}}$ 分别等于$a$ 和$b$ ，第2步（此时$k=1$ ）时计算${\displaystyle r_{-1}}$ （即$b$ ）和$r_{0}$ （第一步计算产生的余数）相除产生的商和余数，以此类推。整个算法可以用如下等式表示：

如果有$a<b$ ，算法的第一步實際上會把兩個數字交換，因為這時$a$ 除以$b$ 所得的商$q_{0}$ 會等于0，余数$r_{0}$ 則等于$a$ 。然後，算法的第二步便是把$b$ 除以$a$ ，再計算所得之商和餘數。所以，對於$k\geq 0$ 總有${\displaystyle r_{k}<r_{k-1}}$ ，即运算的每一步中得出的余数一定小于上一步计算的余数。

由于每一步的余数都在减小并且不为负数，必然存在第$n$ 步时$r_{n}$ 等于0，使算法终止^[21]，${\displaystyle r_{n-1}}$ 就是$a$ 和$b$ 的最大公约数。其中$n$ 不可能无穷大，因为在$r_{0}$ 和0之间只有有限个自然数。

正确性的证明

辗转相除法的正确性可以分成两步来证明。^[20]在第一步，我們會證明算法的最终结果${\displaystyle r_{n-1}}$ 同时整除$a$ 和$b$ 。因为它是一个公约数，所以必然小于或者等于最大公约数$g$ 。在第二步，我們證明$g$ 能整除${\displaystyle r_{n-1}}$ 。所以$g$ 一定小于或等于${\displaystyle r_{n-1}}$ 。两个不等式只在${\displaystyle r_{n-1}=g}$ 时同时成立。

具体证明如下：

1. 證明${\displaystyle r_{n-1}}$ 同時整除$a$ 和$b$ ：

   因爲餘數$r_{n}$ 是0，${\displaystyle r_{n-1}}$ 能夠整除${\displaystyle r_{n-2}}$ ：

   ${\displaystyle r_{n-2}=q_{n}r_{n-1}+r_{n}}$ 

   因爲${\displaystyle r_{n-1}}$ 能夠整除${\displaystyle r_{n-2}}$ ，所以也能夠整除${\displaystyle r_{n-3}}$ ：

   ${\displaystyle r_{n-3}=q_{n-1}r_{n-2}+r_{n-1}}$ 

   同理可證${\displaystyle r_{n-1}}$ 可以整除所有之前步驟的餘數，包括$a$ 和$b$ ，即${\displaystyle r_{n-1}}$ 是$a$ 和$b$ 的公約數，${\displaystyle r_{n-1}\leq g}$ 。

2. 證明最大公約數$g$ 能整除${\displaystyle r_{n-1}}$ ：

   根據定義，$a$ 和$b$ 可以寫成$g$ 的倍數：${\displaystyle a=mg}$ 、${\displaystyle b=ng}$ ，其中$m$ 和$n$ 是自然數。

   因爲${\displaystyle r_{0}=a-q_{0}b=mg-q_{0}ng=(m-q_{0}n)g}$ ，所以$g$ 整除$r_{0}$ 。 同理可證$g$ 整除每個餘數${\displaystyle r_{1},r_{2},\ldots ,r_{n-1}}$ 。

   因爲最大公約數$g$ 整除${\displaystyle r_{n-1}}$ ，因而${\displaystyle g\leq r_{n-1}}$ 。

3. 所以${\displaystyle g=r_{n-1}}$ 。即：^[22][23]

   ${\displaystyle g=\gcd(a,b)=\gcd(b,r_{0})=\gcd(r_{0},r_{1})=\ldots =\gcd(r_{n-2},r_{n-1})=r_{n-1}}$ 

举例

 

算法的演示动画。最初的绿色矩形的长和宽分别是${\displaystyle a=1071}$ 、${\displaystyle b=462}$ ，从中不断铺上462×462的正方形直到剩下部分面积是462×147；然后再铺上147×147的正方形直至剩下21×147的面积；最后，铺上21×21的正方形时，绿色部分就没有了。即21是1071和462的最大公约数。

例如，计算${\displaystyle a=1071}$ 和${\displaystyle b=462}$ 的最大公约数的过程如下：从1071中不断减去462直到小于462（可以减2次，即商${\displaystyle q_{0}=2}$ ），余数是147：

${\displaystyle 1071=2\times 462+147.}$ 

然后从462中不断减去147直到小于147（可以减3次，即${\displaystyle q_{1}=3}$ ），余数是21：

${\displaystyle 462=3\times 147+21.}$ 

再从147中不断减去21直到小于21（可以减7次，即${\displaystyle q_{2}=7}$ ），没有余数：

${\displaystyle 147=7\times 21+0.}$ 

此时，余数是0，所以1071和462的最大公约数是21，这和用素因数分解得出的结果相同（见上文）用表格表示如下：

步骤数	算式	商和余数
0	${\displaystyle 1071=462q_{0}+r_{0}}$	${\displaystyle q_{0}=2}$ 、${\displaystyle r_{0}=147}$
1	${\displaystyle 462=147q_{1}+r_{1}}$	${\displaystyle q_{1}=3}$ 、${\displaystyle r_{1}=21}$
2	${\displaystyle 147=21q_{2}+r_{2}}$	${\displaystyle q_{2}=7}$ 、${\displaystyle r_{2}=0}$ （算法终止）

图形演示

辗转相除法的计算过程可以用图形演示。^[24]假设我们要在${\displaystyle a\times b}$ 的矩形地面上铺正方形瓷砖，并且正好铺满，其中$a$ 大于$b$ 。我们先尝试用${\displaystyle b\times b}$ 的瓷砖，但是留下了${\displaystyle r_{0}\times b}$ 的部分，其中${\displaystyle r_{0}<b}$ 。我们接着尝试用${\displaystyle r_{0}\times r_{0}}$ 的正方形瓷砖铺，又留下了${\displaystyle r_{1}\times r_{0}}$ 的部分，然后再使用${\displaystyle r_{1}\times r_{1}}$ 的正方形铺……直到全部铺满为止，即到某步时正方形刚好覆盖剩余的面积为止。此时用到的最小的正方形的边长就是原来矩形的两条边长的最大公约数。在图中，最小的正方形面积是21×21（红色），而原先的矩形（绿色）边长是1071×462，所以21是1071和462的最大公约数。

计算商和余数

参见：模除和带余除法

在每个步骤$k$ 中，辗转相除法都需要计算两个数$r_{k-1}$ 和${\displaystyle r_{k-2}}$ 的商$q_{k}$ 和余数$r_{k}$ ：

${\displaystyle r_{k-2}=q_{k}r_{k-1}+r_{k}}$ 

其中${\displaystyle 0\leq r_{k}<r_{k-1}}$ 。除法的算法保证这样的商和余数总是存在。自然数的除法算法还指出这样的商和余数是惟一的，但这对辗转相除法而言并非必要。^[25]

在欧几里得最初的描述中，商和余数是通过连续的减法来计算的，即从${\displaystyle r_{k-2}}$ 中不断减去$r_{k-1}$ 直到小于$r_{k-1}$ 。一個更高效的做法是使用整數除法和模除来计算商和余数：

${\displaystyle r_{k}\equiv r_{k-2}{\bmod {r}}_{k-1}}$ 

计算机实现

辗转相除法可用伪代码表示，比如除法版本可以寫成^[26]

function gcd(a, b) while b ≠ 0 t ← b b ← a mod b a ← t return a 

C++版本：

int gcd(int m, int n) {  int t = 1;  while(t != 0) {  t = m % n;  m = n;  n = t;  }  return m; } 

Rust版本：

fn gcd(x: isize, y: isize) -> Option<isize> {  match (x,y) {  (0, 0) => None,  (a, 0) => Some(a.abs()),  (mut a, mut b) => {   while b != 0 {  let t = b;  b = a % b;  a = t;  }   Some(a.abs())   },  } } 

Python 3版本：

def gcd(a, b):  while b != 0:  t = a % b  a = b  b = t  return a 

在第$k$ 次循环开始时，变量$b$ 的值是前一次运算的余数$r_{k-1}$ ，变量$a$ 的值是再前一次运算的余数${\displaystyle r_{k-2}}$ 。步骤${\displaystyle b:=a{\bmod {b}}}$ 的作用等同于递归式${\displaystyle r_{k}\equiv r_{k-2}{\bmod {r}}_{k-1}}$ 。变量$t$ 的功能是在下一个余数$r_{k}$ 计算过程中临时性地保存$r_{k-1}$ 的值。在一次循环结束时，变量$b$ 的值是前一次运算的余数$r_{k}$ ，变量$a$ 的值是再前一次运算的余数$r_{k-1}$ 。

在欧几里得定义的减法版本，取餘运算被减法替换。^[27]

function gcd(a, b) if a = 0 return b while b ≠ 0 if a > b a ← a − b else b ← b − a return a 

变量$a$ 和$b$ 的值分别是前两次的余数$r_{k-1}$ 和${\displaystyle r_{k-2}}$ 。假定第$k$ 次循环开始时$a$ 大于$b$ ，那么$a$ 等于${\displaystyle r_{k-2}}$ ，因为${\displaystyle r_{k-2}>r_{k-1}}$ 。在循环过程中，$a$ 重复减去$b$ 直到比$b$ 小，此时$a$ 就是下一个余数$r_{k}$ ；然后$b$ 重复减去$a$ 直到比$a$ 小，此时$b$ 就是下一个余数${\displaystyle r_{k+1}}$ ；重复执行直到$b=0$ 。

以下是递归版本^[28]：

function gcd(a, b) if b = 0 return a else return gcd(b, a mod b) 

C++递归版本如下：

int gcd(int n,int m) {  return m == 0 ? n : gcd(m, n % m); } 

Rust递归版本：

fn gcd(x: isize, y: isize) -> Option<isize> {  match (x,y) {  (0, 0) => None,  (a, 0) => Some(a.abs()),  _ => gcd(y, x % y),  } } 

Java版本：

public class MethodOfSuccessiveDivision {  public static void main(String[] args) {  System.out.println(gcd(1071, 462));  }  public static int gcd(int a, int b){  if(b == 0){  return a;  }else{  return gcd(b, a % b );  }  } } 

Python 3版本：

def gcd(a, b):  return a if b == 0 else gcd(b, a % b) 

例如${\displaystyle \gcd(1071,462)}$ 的计算过程是：函数的第一次调用计算${\displaystyle \gcd(462,1071{\bmod {4}}62)=\gcd(462,147)}$ ；下一次调用计算${\displaystyle \gcd(147,462{\bmod {1}}47)=\gcd(147,21)}$ ，在接下来是${\displaystyle \gcd(21,147{\bmod {2}}1)=\gcd(21,0)=21}$ 。

使用绝对值最小的余数

在另一个版本的算法中，每一步还要把取余运算时计算出的商增加一后再重新计算余数（此时计算出的余数应该是负的），然后取两个余数的绝对值较小的数作为下一步运算时使用的余数。^[29][30]取余运算后，设$r_{k}$ 是计算出的余数（此時為正），$q$ 是计算出的商：

${\displaystyle r_{k-2}=q_{k}r_{k-1}+r_{k}}$ 

即假設${\displaystyle r_{k-1}>r_{k}>0}$ 。然後使用以下式子计算出一个负的余数$e_{k}$ ：

${\displaystyle r_{k-2}=(q_{k}+1)r_{k-1}+e_{k}}$ 

如果${\displaystyle |e_{k}|<|r_{k}|}$ ，那么用$e_{k}$ 替换$r_{k}$ 进行下一次运算。如利奥波德·克罗内克所指出的，这个版本需要的运算步骤是欧几里得算法的所有版本中最少的。^[29][30]

历史发展

 

辗转相除法可能在欧几里得之前几个世纪就已经有了。图为使用两脚规进行测量。

辗转相除法是目前仍然在使用的历史最悠久的算法之一。^[31]它首次出现于《几何原本》（卷7命题1–2、卷10命题2–3）（大约公元前300年）。在卷7中用于整数，在卷10中用于线段的长度（以現代的觀點看，线段的长度可視為正实数，也就是說辗转相除法實際可用於實數上，但是当时未有实数的概念）。卷10中出现的算法是几何的，两段线段a和b的最大公约数是a和b的公度中的最大值。

这个算法可能并非欧几里得发明，因為他也有将先前其他數學家的一些成果编进他的《几何原本》。^[32][33]数学家、历史学家范德瓦尔登（英语：Bartel Leendert van der Waerden）认为卷7的内容可能来自毕达哥拉斯学院出身的数学家写的关于数论的教科书。^[34]辗转相除法在當時很可能已為尤得塞斯（大約公元前375年）所知 ^[31][35]，甚至可能更早之前就已经存在^[36][37]，因为欧几里得和亚里士多德的著作中都出现了ἀνθυφαίρεσις一词（意为“辗转相减”）。^[38]

几个世纪之后，辗转相除法又分别被中国人和印度人独立发现，^[39]主要用来解天文学中用到的丢番图方程以及制定准确的历法。5世纪末，印度数学家、天文学家阿里亚哈塔曾稱辗转相除法为“粉碎机”，這可能是因为它在解丢番图方程时很有效^[40]。^[41]在中国，《九章算术》中提到了一种类似辗转相减法的“更相减损术”^[42]。《孙子算经》中則出现了中国剩余定理的一个特例^[43]，但是直到1247年秦九韶才於其《数学九章》中解答了該定理的一般情況，當中用到了他發明的大衍求一术。此法的其中一部分實際上便是輾轉相除的原理，秦九韶在書中對此有明確表述。^[44]在欧洲，辗转相除法首次出现于克劳德·巴希特（英语：Claude Gaspard Bachet de Méziriac）的著作《愉悦讨喜的问题》（Problèmes plaisants et délectables）的第二版^[41]在欧洲，辗转相除法被用于丢番图方程和構建连分数。后来，英国数学家桑德森（英语：Nicholas Saunderson）在其著作中收編了扩展欧几里得算法，作为一個有效计算连分数的方法。他將此法的來源歸名於罗杰·科茨（英语：Roger Cotes）。^[45]

19世纪，辗转相除法促成了新数系的建立，如高斯整数和艾森斯坦整数。1815年，高斯用辗转相除法证明高斯整数的分解是惟一的，儘管他的研究到了1832年才首度发表。^[46]高斯在他的《算数研究》（出版于1801年）中實際上也有援引这个算法，但僅是以连分数方法的形式敘述。^[39]约翰·狄利克雷是第一个将辗转相除法作为数论的基础的数学家。^{[來源請求]}狄利克雷提出，数论中的很多结论，如分解的惟一性，在任何使辗转相除法適用的数系中均有效。^[47]狄利克雷的數論講義後來經理查德·戴德金編輯和推广，戴德金也有以辗转相除法來研究代数整数。比如，他是第一个用高斯整数的分解惟一性证明费马平方和定理的数学家。^[48]戴德金还率先定义了欧几里得整环的概念。19世纪末，戴德金所定義的理想概念使得數論的重心不必建基於輾轉相除法，從而促進了理論的發展。^[49]

“欧几里得算法是所有算法的鼻祖，因为它是现存最古老的非凡算法。”

——高德纳，《计算机程序设计艺术，第二卷：半数值算法》，第二版 (1981), p. 318.

辗转相除法的其他应用发展于19世纪。1829年，施图姆将辗转相除法用于施图姆序列（用于确定多项式的不同实根的个数的方法）。^[50]

辗转相除法是历史上第一个整数关系算法（英语：integer relation algorithm），即寻找两個可通約實數的整数关系的算法。近年来，出现了一些新颖的整数关系算法，如埃拉曼·弗格森（英语：Helaman Ferguson）和福尔卡德于1979年发表的弗格森-福尔卡德算法（Ferguson–Forcade algorithm） ^[51]、以及与它相关的LLL算法（英语：Lenstra–Lenstra–Lovász lattice basis reduction algorithm）、HJLS算法以及PSLQ算法。^[52][53]

1969年，科尔（Cole）和戴维（Davie）基于辗转相除法创造了一种二人游戏，叫做「欧几里得游戏」。^[54]这个游戏有最优策略。^[55]游戏开始于两列分别为a和b个棋子组成的序列，玩家轮流从较长一列中取走较短一列棋子数量的m倍的棋子。如果两列棋子p和q分别由x和y个棋子组成，其中x大于y，那么玩家可以將序列p的棋子数量减少为自然数x − my。最后率先将一列棋子清空的玩家胜出。^[56][57]

数学上的应用

贝祖等式

贝祖等式说明，两个数$a$ 和$b$ 的最大公约数$g$ 可以表示为$a$ 和$b$ 的线性和。^[58]也就是说，存在整数$s$ 和$t$ 使${\displaystyle g=sa+tb}$ 。^[59][60]

整数$s$ 和$t$ 可以从辗转相除法算出的商${\displaystyle q_{0},q_{1},\cdots }$ 计算出。^[61] 从辗转相除法的最后一步开始，$g$ 可以表示成前一步的商${\displaystyle q_{N-1}}$ 和前两步的余数${\displaystyle r_{N-2}}$ 和${\displaystyle r_{N-3}}$ ：

${\displaystyle g=r_{N-1}=r_{N-3}-q_{N-1}r_{N-2}}$ 

而前两步的余数又分别可以表示成它们前两步的余数和商：

${\displaystyle r_{N-2}=r_{N-4}-q_{N-2}r_{N-3}}$ 

${\displaystyle r_{N-3}=r_{N-5}-q_{N-3}r_{N-4}}$ 

将这两行式子先後代入第一个式子，可以将$g$ 表示成${\displaystyle r_{N-4}}$ 和${\displaystyle r_{N-5}}$ 的线性和。重复进行迭代直到出现$a$ 和$b$ ：

${\displaystyle r_{2}=r_{0}-q_{2}r_{1}}$ 

${\displaystyle r_{1}=b-q_{1}r_{0}}$ 

${\displaystyle r_{0}=a-q_{0}b}$ 

最终，g可以表示成$a$ 和$b$ 的线性和：${\displaystyle g=sa+tb}$ 。贝祖等式以及以上证明都可以扩展至欧几里得整环。

主理想和相关问题

贝祖等式提供了另一种定义$a$ 和$b$ 的最大公约数$g$ 的方法。^[11]考虑形如${\displaystyle ua+vb}$ （其中$u$ 和$v$ 是整数）的数的集合。因为$a$ 和$b$ 都可以被$g$ 整除，所以这个集合中的所有元素都可以被$g$ 整除。也就是说这个集合中的数都可以表示成$g$ 的倍数，或者$a$ 和$b$ 的其他公约数的倍数。但是，只有最大公约数才是这个集合的元素。根据贝祖等式，有${\displaystyle g=sa+tb}$ 。換言之，当${\displaystyle u=s}$ 、${\displaystyle v=t}$ 时得出$g$ 。任何其他的公约数都不是这个集合的元素，因为它们都不能被比它们大的$g$ 整除。相反地，$g$ 的任何倍数都属于这个集合，只要令${\displaystyle u=ms}$ 、${\displaystyle v=mt}$ ，便有：

${\displaystyle mg=msa+mtb}$ 

所以，形如${\displaystyle ua+vb}$ 的数的集合等于$g$ 的整数倍的集合。也就是说，任意两个数的线性和的集合等同于它们最大公约数的整数倍的集合。$a$ 和$b$ 的最大公约数叫做$a$ 和$b$ 的理想的生成元素。这个最大公约数的定义导出了兩個现代抽象代数的概念：主理想（由单个元素生成的理想）以及主理想整环（其每一理想都是主理想的整环）。

这个结果可以解决某些實際问题。^[62]例如，考虑两个容积分别为$a$ 和$b$ 的量杯，其中$a$ 和$b$ 為正整數。通过加入或倒去$u$ 倍第一个量杯的体积以及$v$ 倍第二个量杯的体积的液体，任何体积为${\displaystyle ua+vb}$ 的液体都可以被量出（只要${\displaystyle ua+vb}$ 為正數）。根據贝祖等式，凡是可以被量出的液体，其体积一定是$a$ 和$b$ 的最大公约数$g$ 的倍數。

扩展欧几里得算法

主条目：扩展欧几里得算法

贝祖等式的整数s和t可以通过扩展欧几里得算法算出。这个扩展算法在原有辗转相除法的基础上增加了两个递归等式：^[63]

${\displaystyle s_{k}=s_{k-2}-q_{k}s_{k-1}}$ 

${\displaystyle t_{k}=t_{k-2}-q_{k}t_{k-1}}$ 

算法开始时：

${\displaystyle s_{-2}=1}$ , ${\displaystyle t_{-2}=0}$ 

${\displaystyle s_{-1}=0}$ , ${\displaystyle t_{-1}=1}$ 

加上这兩个递归式后，当算法终止于${\displaystyle r_{N}=0}$ ，贝祖等式的整数$s$ 和$t$ 分别由${\displaystyle s_{N}}$ 和${\displaystyle t_{N}}$ 给出。

这个算法的正确性可以用数学归纳法来证明。假设递归至第$k-1$ 步是正确的，也就是假设：

${\displaystyle r_{j}=s_{j}a+t_{j}b}$ 

在$j$ 小于$k$ 時皆成立。则第$k$ 步运算得出以下等式：

${\displaystyle r_{k}=r_{k-2}-q_{k}r_{k-1}}$ 

因为${\displaystyle r_{k-2}}$ 和$r_{k-1}$ 被假定是正确的，所以可以用$s$ 和$t$ 表示：

${\displaystyle r_{k}=(s_{k-2}a+t_{k-2}b)-q_{k}(s_{k-1}a+t_{k-1}b)}$ 

整理后得到第$k$ 步的结果，和我们期望得到的结果一致：

${\displaystyle r_{k}=s_{k}a+t_{k}b=(s_{k-2}-q_{k}s_{k-1})a+(t_{k-2}-q_{k}t_{k-1})b}$ 

矩阵法

整数$s$ 和$t$ 也可以用矩阵运算得出。^[64]辗转相除法的计算过程：

${\displaystyle a=q_{0}b+r_{0}}$ 

${\displaystyle b=q_{1}r_{0}+r_{1}}$ 

...

${\displaystyle r_{N-2}=q_{N}r_{N-1}+0}$ 

可以写作2×2的商矩阵乘以一个2维余数向量：

${\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}$ 

令$\mathbf {M}$ 表示所有商矩阵的乘积：

${\mathbf {M} }={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}$ 

这使辗转相除法化简为：

${\begin{pmatrix}a\\b\end{pmatrix}}={\mathbf {M} }{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}={\mathbf {M} }{\begin{pmatrix}g\\0\end{pmatrix}}$ 

如要用$a$ 和$b$ 的线性和表示$g$ ，可將等式两边同时乘以矩阵$\mathbf {M}$ 的逆矩阵。^[64][65]$\mathbf {M}$ 的行列式等于${\displaystyle (-1)^{N+1}}$ ，因为它等于商矩阵的行列式的乘积，而每一个的行列式都是−1。因为$\mathbf {M}$ 的行列式不为零，最终的余数向量可以利用$\mathbf {M}$ 的逆矩阵解出：

${\begin{pmatrix}g\\0\end{pmatrix}}={\mathbf {M} }^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}$ 

由上式可以得出${\displaystyle g=(-1)^{N+1}(m_{22}a-m_{12}b)}$ 。

贝祖等式中的两个整数分别是${\displaystyle s=(-1)^{N+1}m_{22}}$ 、${\displaystyle t=(-1)^{N}m_{12}}$ 。矩阵法的效率可前文描述的辗转相除法的递归算法是相同的，每一步都有两次乘法和两次加法。

欧几里得引理和唯一分解

贝祖等式对辗转相除法的很多应用都很重要，如证明自然数的唯一分解性质^[66]假设数字L可以写成两个因数$u$ 和$v$ 的乘积，即${\displaystyle L=uv}$ 。如果另一个数$w$ 与$u$ 互素的数也能整除$L$ ，那么$w$ 必须整除$v$ ，证明如下：如果$u$ 和$w$ 的最大公约数是1，则根据贝祖等式存在$s$ 和$t$ 使

${\displaystyle 1=su+tw}$ 。

两边都乘以$v$ ：

${\displaystyle v=suv+twv=sL+twv}$ 

因为$w$ 整除等式右边，所以也应整除等式左边的$v$ 。这个结果叫做欧几里得引理。^[67]如果一个素数整除$L$ 那么它至少整除$L$ 的一个因数。如果一个数$w$ 互素于数列${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$  中的每一个数，则w也一定互素于它们的乘积${\displaystyle a_{1}\times a_{2}\times \ldots \times a_{n}}$ 。^[67]

欧几里得引理足以证明每一个自然数的素数分解是惟一的。^[68]我们用反证法来证明，假设$L$ 可以分别分解成$m$ 个素数和$n$ 个素数，即：

${\displaystyle L=p_{1}p_{2}\cdots p_{m}=q_{1}q_{2}\cdots q_{n}}$ 

根据假设，每个素数$p$ 都能整除$L$ ，因此它必须能够整除某個$q$ ；因为$q$ 也是一个素数，所以$p=q$ 。同理，对于每一个$p$ 都存在一个$q$ 与它相等。所以两种分解除了顺序不同以外是完全相同的。整数分解的惟一性在数学证明中有很多应用，下文将会提到。

线性丢番图方程

 

线性丢番图方程：${\displaystyle 9x+12y=483}$ 的图像，它的解用蓝点表示。

丢番图方程是以亚历山大数学家丢番图的名字命名的一类方程，它的解被限制在整数范围。^[69]关于整数$x$ 和$y$ 的线性丢番图方程形如：^[70]

$ax+by=c$ 

其中$a$ 、$b$ 、$c$ 是已知整数。这个方程可以写成关于$x$ 的同余式：

${\displaystyle ax\equiv c{\pmod {b}}}$ 

令$g$ 为$a$ 和$b$ 的最大公约数，$a$ 、$b$ 都能被$g$ 整除，故$ax+by$ 能够被$g$ 整除。所以，$c$ 一定能够被$g$ 整除，不然方程就无解。方程两边若同时除以 ${\displaystyle {\frac {c}{g}}}$ ，方程就变成了贝祖等式：

$sa+tb=g$ 

其中$s$ 和$t$ 可以用扩展欧几里得算法求解。^[71]所以这个丢番图方程的一个解即是：

${\displaystyle {\begin{aligned}x_{1}=s({\frac {c}{g}})\\y_{1}=t({\frac {c}{g}})\end{aligned}}}$ 

总体而言，丢番图方程如果有解，就一定有无数个解。^[72]只需要考虑两个解$(x_{1},y_{1})$  和$(x_{2},y_{2})$ ：

$ax_{1}+by_{1}=c=ax_{2}+by_{2}$ 

或者可以写成：

$a(x_{1}-x_{2})=b(y_{2}-y_{1})$ 

所以相邻两个解的$x$ 之间的差是${\displaystyle {\frac {b}{g}}}$ ，$y$ 之间的差是${\displaystyle {\frac {a}{g}}}$ 。这样，所有的解都可以表示成：

${\displaystyle {\begin{aligned}x=x_{1}-{\frac {bt}{g}}\\y=y_{1}+{\frac {at}{g}}\end{aligned}}}$ 

当${\displaystyle t}$ 取遍所有整数时，方程所有的解都可以从$(x_{1},y_{1})$ 计算出来。如果限制為正整数解 (${\displaystyle x>0}$ , ${\displaystyle y>0}$ ) 的话，那么解的数量就可能是有限的。有時候，这种对解的限制使丢番图方程在未知数個數比方程數更多的情况下仍然能有唯一解^[73]，而在允許實數解的线性方程组中，这種情況是不可能的。

乘法逆和RSA算法

有限域是一个支持四种运算的数集。这四种运算也通稱為加法、减法、乘法、除法，跟一般的四則運算有相同的性质，如交换律、结合律和分配律。举例来说，使用同余可以让13个数字的集合 ${\displaystyle \{0,1,2,\cdots ,12\}}$  构成一个有限域。在这个域中，任何数学运算（加减乘除）都归约成13的模，例如 ${\displaystyle 5\times 7=35{\bmod {1}}3=9}$ 。对于任意素数${\displaystyle p}$ ，都可以定义这种有限域；使用更复杂的方法，也可以对素数${\displaystyle p}$ 的${\displaystyle m}$ 次方定义这样的有限域。有限域也叫做伽罗瓦域，其缩写為 ${\displaystyle \mathrm {GF} (P)}$  或${\displaystyle \mathrm {GF} (P^{m})}$ 。

在这样一个有${\displaystyle m}$ 个数的域中，任何非零元素${\displaystyle a}$ 都存在惟一乘法逆 ${\displaystyle a^{-1}}$ 使${\displaystyle aa^{-1}=a^{-1}a\equiv 1{\bmod {m}}}$ 。这可以通过解同余式${\displaystyle ax\equiv 1{\bmod {m}}}$ 得出，^[74]或者也可以解与之等价的丢番图方程^[75]

${\displaystyle ax+my=1}$ 

这个方程可用扩展欧几里得算法解出（参见上文）。在RSA算法中，寻找乘法逆是非常重要的一步，它决定了使用哪个数来解密信息。

七月 13, 2023