注意:阅读该文章需要一点点的群论基础。
这里先放一些前置定义和定理及其证明:
合成法则:集合 S 上的合成法则就是将 S 中的元素a,b结合成另外一个元素,比如说p,规范地说,合成法则是一个有两个变量的是函数或映射S\times S\rightarrow S。
群:
一个群是一个带有下列性质的合成法则(这里说明了群的计算封闭性)的集合G:
1、合成法则满足结合律:(ab)c=a(bc)对G汇总任意a、b、c成立(这里的ab并不是表示a与b在实数意义下的乘积,只是一种任意定义的二元运算,叫做“乘法”)。
2、G中包含单位元1(这也不是实数意义上的1,只是一个表示“乘法”的单位元记号),使得对于G中任意元素a有1a=a1=a。
3、G中任意元素均有逆,即存在元素b使得ab=ba=1。
子群:
群G的子集H称为一个子群,如果它具有下列性质:
1、封闭性:若 a\in H 并且 b\in H ,则 ab\in H 。
2、恒等元: 1\in H 。
3、逆元:若 a\in H ,则 a^{-1}\in H 。
整数加群 Z^+ :整数集合,整数加法作为它的复合法则。
该群的子群 S 必满足以下三个性质:
1、封闭性:如果 a,b\in S ,则 a+b\in S 。
2、单位元: 0\in S 。
3、逆元:若 a\in S ,则 -a\in S 。
定义:设 a 是异于0的整数,记由所有a的倍数构成的Z的子集:
Za=\{n\in Z|存在k\in Z,使n=ka\}
定理:令 S 是整数加群 Z^+ 的子群,则 S 或为平凡子群{0},或是有形式 Za ,其中a为 S 中最小正整数。
证明:
令 S 是 Z^+ 的一个子群,则 0\in S 。
如果0是 S 中唯一的元素,则 S 为平凡子群,因而对这一情形结论成立。
否则, S 包含异于0的整数n,且要么n是正数,要么-n是正数。由子群的第三个性质可知: -n\in S ,故 S 含有正整数。
首先证明 Za 是 S 的子集,即 ka\in S 对于任意整数k成立。
如果k是正整数,
则 ka = a + a + ... + a(k项) 。
由于 a\in S ,由子群的封闭性和归纳法知 ka\in S 。子群中元素的逆元仍属于 S ,因此 -ka\in S 。最后, 0a=0\in S ,因此 Za\subseteq S 。
其次,证明 S 是 Za 的子集,即 S 中任意元素n是a的整数倍。用带余除法,记 n=qa+r ,其中q、r都是整数且余数r的取值范围为 0\leq r \lt a 。
由于 Za\subseteq S 且 qa\in Za ,故 qa\in S 。
同时,因为 n\in S 且 r=n-qa ,由 S 群的封闭性性质可知, r\in S 。又因为 a 为 S 中最小的正整数,而余数r满足 0\leq r \lt a ,故 r=0 ,因此n的形式一定为 n=qa ,故 S\subseteq Za ,由 Za\subseteq S ,可知 S=Za 。
证毕
现在开始证明辗转相除法的正确性
定义: S=Za+Zb=\{n\in Z|n=ra+sb,r\in Z,s\in Z\} (a,b为整数且不同时为0)
S 显然是 Z^+ 的子群。
上述定理说明,一定存在一个正整数d,使得 S=Zd ,其中d是 S 中最小的正整数。
显然, a\;mod \; d=0 且 b\;mod \; d=0 ,也就是说,d是a和b的公因数。
并且,若存在整数e,使得 a\;mod \; e=0 且 b\;mod \; e=0 ,则必然使 (ra+sb)\;mod\;e=0 。
因为d在群 S 中,因此存在整数r和s使 d=rs+sb ,故 d\;mod\;e=0 。
为使这个条件成立,显然 d\geq e ,由于e的任意性(显然 e\leq a 且 e\leq b 且e是a与b的公因数),则 d=max\{e\}=gcd(a,b) (否则必然存在 e=gcd(a,b) ,使得上述结论不成立),也就是说,d是a与b的最大公因数(显然,d的这一取值是满足上述全部性质的,因此为唯一解)。
欧几里得辗转相除法证明:
假设,我们要求正整数a与b的最大公因数,则 a=qb+r ,由于群 S 是a与b的线性组合群,且由上式显然可知,a与b线性组合的一切数均可用b与r的线性组合表示( ma+nb=m(qb+r)+nb=mqb+mr+nb=(mq+n)b+mr ),因此, Za+Zb=Zb+Zr ,由于这两个线性组合群是等价的,又因为存在一个 d=gcd(a,b) 使得 Za+Zb=Zd ,也存在一个 e=gcd(b,r) 使得 Zb+Zr=Ze ,故 d=e 或者说 gcd(a,b)=gcd(b,r) 。
因为任意一个正整数经过因子分解都至少存在一个因子1,所以任意两个正整数的最大公因数一定存在且至少为1。
根据辗转相除法, gcd(a,b) 经过有穷次变换之后必然可以变换为 gcd(p,q) ,其中 p=kq(k\in N^+) (如若依然存在余数r,则必然可以继续分解,随着不断分解,p、q和r会逐渐减小,且 r \lt q \lt p ,则必然有一个时刻 r=0 ),那么此时显然 gcd(p,q)=q ,由上述 gcd(a,b)=gcd(b,r) 可知, gcd(a,b)=gcd(p,q)=q 。