欧几里得辗转相除法的正确性证明

注意:阅读该文章需要一点点的群论基础。

这里先放一些前置定义和定理及其证明:

合成法则:集合 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

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据