在几何原本卷十命题三中已知两个可公度的量计算它们的最大公度量欧几里得给出了递归解法设两条线段a,b可公度如果它们相等则最大公度就是其中任意一条线段此时算法返回a作为结果如果线段a比b长就用圆规不断从a中截去b然后求截端后的线段a和b的最大公度如果线段b比a长就反过来不断从b中截去a,然后求截端后的线段b和a的最大公度.由于ab时,a mod b a公式可以进一步写成示意如下计算gcd(24, 110)2的过程程序实现gcda b gcdb a % b gcd(a%b, b %(a%b)) ....先上辗转相除法欧几里得算法的三种代码实现#include stdio.h #include stdlib.h int gcd1(int a, int b) { int ret; while(1) { if(a b) { a a%b; if(a 0) { ret b; break; } } else { b b %a; if(b 0) { ret a; break; } } } return ret; } int gcd2(int a,int b) { if(b 0) return a; return gcd2(b,a%b); } int gcd3(int a,int b) { while(b){ int t b; b a%b; a t; } return a; } int main(void) { int a, b; a 100; b 45; printf(%s line %d, res1 %d, res2 %d, res3 %d.\n, __func__, __LINE__, gcd1(a, b), gcd2(a, b), gcd3(a, b)); return 0; }下面用一幅图示解题过程图中蓝色的矩形单元表示一个最小公约的单元。它具有以下性质1.以最小公约表示的两个原数字互质。这是必然反证法如果不互质则可以提取一个共同的因子重新定义最小公约单元直到表示为互质比如图中的8和3互质。2.辗转相除的每个阶段的两个数字也均互质证明过程类似反正法即可当前辗转阶段如果存在共同的约数则必然传递到之前的阶段也都有同样的约数所以同理最小公约单元也要重新定义直到每级辗转互质。基于以上两个严密的逻辑辗转相除一定能够找到组成两个数字的最基本的公约块儿它是两个数字共有的零件。扩展-求最小公倍数既然上一步已经计算得到了最小公约数并且得到了以最小公约表示的两个原数字互质的推论就不难得到计算最小公倍数的公用公式。通用算法已知数字m,n的最大公约数是g,则m/g, n/g互质两个互质的数的最小公倍数就是两个质数之积所以最小公倍数为由于单元为g,所以最小公倍数的真实值为#include stdio.h #include stdlib.h int gcd1(int a, int b) { int ret; while(1) { if(a b) { a a%b; if(a 0) { ret b; break; } } else { b b %a; if(b 0) { ret a; break; } } } return ret; } int gcd2(int a,int b) { if(b 0) return a; return gcd2(b,a%b); } int gcd3(int a,int b) { while(b){ int t b; b a%b; a t; } return a; } int lcm1(int a, int b) { int g_c_d gcd1(a, b); return a*b/g_c_d; } int lcm2(int m, int n) { int mn, r ; if(mn){ mn m ; m n ; n mn; } mn m * n ;//俩个数的乘积 r m % n ; while(r!0){ m n ; n r ; r m % n ; } return mn/n; //n为最大公约数 } int main(void) { int a, b; a 100; b 45; printf(%s line %d, res1 %d, res2 %d, res3 %d, lcm1 %d, lcm2 %d.\n, __func__, __LINE__, gcd1(a, b), gcd2(a, b), gcd3(a, b), lcm1(a, b), lcm2(a,b)); return 0; }main line 84, res1 5, res2 5, res3 5, lcm1 900, lcm2 900.图解LCM of 32, 48 and 72 2 × 2 × 2 × 2 × 2 × 3 × 3 288关于两个互质数的最小公倍数是两数之积可以证明如下假设a,b两数互质也就是两数没有1以外的公约数则最小公倍数是axb.不失一般情况假设ab,则a的倍数从小到大排列为a,2a,3a,......(b-1)a, ba;在ba之前的所有a的倍数中假设ka(1kb)同样也是b的倍数则是整数。由于a,b互质则a/b不可能存在导致结果为整数的因子所以只有k存在这个因子但是k小于b,所以同样得到结论这样的K不存在这样最小的公倍数只能是ab了结论得证。或者用反证法我们知道ab一定是公倍数要证明是最小其它公倍数对最小公倍数之间一定可以整除其他公倍数之间不一定所以假设ab/n是其最小公倍数则根据ab/n整除a,b可以推理出n是a,b的公因数这和a,b互质矛盾。上面那句虽然结论正确,但是推理显然是错误,反例如下40*5/25 8. 但是40和5任何一个都不能整除25,所以得不到ab/n整除,n是a,b公因数的结论.倒是可以证明:ab/n为整数,则a,b一定不互质,因为假如a,b互质,则设mab,ab为m的一个质因数分解.根据算数基本定理,这个指因数分解唯一.如果存在cab/nm/n,则必然存在mcn,n小于a,b的情况下则m又引入了一个非a,b的因子n和c,不管n,c是质数还是合数,都违背了算数基本定理的唯一性要求.所以得证.PS只有当a,c互质且ab/c整除时才能得出b/c整除的结论40*5/25由于无论40或者5都和25不互素所以不适用于这个结论无论40或者5都无法整除25.关于这个定义初等数论中的描述如下如果a,b和c是正整数满足(a,b)1.且a|bc,则a|c.证明如下由于(a,b)1也就是a,b互素存在整数x,y,使得axby1,等式两边同时乘以c得到acxbcyc.由于bc能够整除a所以a*cxbc*y实际上是两个能够整除a的整数的线性组合cx,y为系数所以a*cxbc*y也能够整除a. 而a*cxbc*y等于什么呢它就等于c所以a|c. 结论得到证明。或者通过欧几里德定理证明素数的唯一分解角度(a,b)1.且a|bc如果将a,b,c三个数字进行欧几里德素数分解则a,b互素所以它们一定没有除1以外的共因子。 因此c必须包含所有a的素因子并且唯一因此a一定能够整除c.总结基本原理两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。个人解析若A、B有最大公约数KA B)则A、B、A - B、A mod BA / B的余数都是K的倍数。即余数A - B和 B 的最大公公约数也是 K 。由此递归可知当 A mod B 0即 A 是 B 的倍数时此时B 即为 K 。实际上存在如下定理两数最大公约数与最小公倍数的积等于两数之积用公式表示就是当时实际上有更普遍的结论最大公因数*最小公倍数pq。这个证明过程也很简单假设a,b互质那么它们的最小公倍数是ab,最大公因数1满足题设。当整数a和b的最小公倍数就是他们的乘积ab时则他们也是互素的。假如a,b不互质则必然存在质数p,q (p,q)1,sgcd(a,b),使的a sp,bsq, s为整数。则最小公倍数为spq,最大公约数为s.s*spq sp*sq a*b同样满足题设。这个结论用整数的质因数分解更加容易。这个证明需要的引理(p,q)1则lcmpq可以根据算数基本定理证明(p,q)1说明,p,q的素分解式中不存在相同的素数否则他们的(p,q)1必定不成立要么某个相同的素数要么某几个相同的素数之积所以他们的lcm一定是所有p,q的素因子之积而素因子又不存在交集所以lcm一定是pxq.图形化表示辗转相除获取最大公约数证明: gcd(a,b) gcd(b, a%b).设cgcd(a,b). 则a mcb nc并且m,n互素假如m,n有公因子则一定可以抽取出来和c作乘积产生新的最大公约数而前提我们已经设定c为最大公约了所以一定有办法让m,n互素).aqbrmcqncr rmc-qnc (m-qn)c.所以c仍然是a%b的因子。又因为m-qn和n互素证明如下假如m-qn和n有非1公因子s,gcd(n, m-qn) s, nxs, m-qnys.则r(m-qn)c ysc, aqxscysc, b xsc.所以a,b的公因子是少是sc而非c. 或者这样理解m-qnx*s, ny*sm(qyx)s,所以m,n有公因子s和m,n互素矛盾所以m-qn和n互素。所以bnc和a%b(m-qn)c的最大公因子也是c否则n和m-qn一定能抽取另一个公因子和C相乘得到新的最大公因子矛盾。所以 gcd(a,b) gcd(b, a%b).b, a%b和a,b有相同的最大公因子。从下图也可以看出如果某级运算出现了新的更大的公约数则这个公约数一定会反推回a,b导致更新前提所以GCD的运算会保持最大公约数不变。下图展示了欧几里得算法的一个几何解释反复剪掉正方形用最终的小正方形铺满整个原图。以上图形化证明过程的代码表达如下设初始两个自然数为a,b, 并且abb非0可以证明存在两个唯一的整数 q 和 r满足 a q*b r , q 为整数且0 ≤ |r| |d|。其中q 被称为商r 被称为余数a,b分别被除数和除数取余运算求取的就是这个余数r。只要a,b是可公度的这些式子不会无限列下去从r0开始每一步r(n1)是r(n)的余数r(n1) r(n),但是r0是自然数起始值是有限的所以这个过程不可能无限进行下去最后一步总归能够整除最后一步的除数r(n2)就是最大公约数。往回迭代.........下一步证明任何a,b的公度c,一定可以度量r(n2).由于c是公度因此a,b都可以用它来表示m,n为自然数这样上面的式子可以写成.....所以r0,r1,.....r(n),r(n1), r(n2)都可以由c来公度所以r(n2)是最大公度。以本片开头的例子为例计算110和24的最大公约数a110,b24.a110,b24.1104*2414.241*1410.141*104.102*42.42*2 0.定理得证。裴蜀定理裴蜀定理或贝祖定理得名于法国数学家艾蒂安·裴蜀说明了对任何整数a ,b 和它们的最大公约数d,关于未知数x和y 的线性不定方程称为裴蜀等式):若a ,b 是整数,且gcd(a,b)d,那么对于任意的整数x ,y , axby都一定是d的倍数特别地一定存在整数x,y使axbyd成立,对于a,b互素的情况一定存在x,y使的axby1.可以这样抽象理解每次a mod bm余r的过程都是所以.......也就是说通过GCD计算最大公约数的过程就是计算a,b线性组合的过程系数分别为x,yraxby.计算gcd(a,b)axby所需的x,y:......方程是不定方程无法限定x,y.符合要求的x,y可以构成一个一维空间在一条直线上但是满足x,y为整数的并不多。另外对于axbyk形式的直线如果a,b互质则K可以为任意整数但是如果a,b的最小公因数大于1则小于其最公因数的数字不能被表示。可以简单证明如下axbyk, anc, bmc. 则ncxmcykc(nxmy)k,n,m互质所以能表示任意整数。((m,n)1,则存在 mxby1,两边同时乘以任意整数则可以表示任意数在乘以一个c则只能表示sc了,s是整数。不能表示任意整数了。在使用欧几里德算法计算GCD时每一步得到的两个数字GCD都和初始两个数字的GCD相同所以每一步的两个数字p,q均可应用贝祖定理。假设第k层则第k1层:所以展开:对照第K层所以并且在最后一次的迭代中一定是,编程得到#includestdio.h #includestdlib.h //注意ab必须互质 int ex_gcd(int a, int b, int *x, int *y) { int x1, y1, r; if(b 0) { if(a! 1) { printf(%s line %d, error, a %d is not 1 in last recursive.\n, __func__, __LINE__, a); exit(-1); } *x 1; *y 0; return a; } r ex_gcd(b, a % b, x1, y1); *y x1 - a / b * y1; //根据推导的每层xy的关系而来 *x y1; //同上 return r; } int main(void) { int a, b, x, y; while(~scanf(%d%d, a, b)){ int ret ex_gcd(a, b, x, y); printf(x : %d, y : %d, ret %d\n, x, y, ret);//其实ret就是ab的最大公约数 printf(%d * %d %d * %d %d\n, a, x, b, y, a * x b * y); } return 0; }下图展示了两个整数6和9的最大共因子是两个整数的线性组合的最小正整数这个事实程序中关于输入的两个数必须互质的条件可以拿掉因为互质的情况下1是两个数的最大公约数拿掉的话程序的通用性更强得到的x,y会普适下列形式的贝祖定理axby gcd(a,b)#includestdio.h #includestdlib.h int ex_gcd(int a, int b, int *x, int *y) { int x1, y1, r; if(b 0) { #if 0 if(a! 1) { printf(%s line %d, error, a %d is not 1 in last recursive.\n, __func__, __LINE__, a); exit(-1); } #endif *x 1; *y 0; return a; } r ex_gcd(b, a % b, x1, y1); *y x1 - a / b * y1; //根据推导的每层xy的关系而来 *x y1; //同上 return r; } int main(void) { int a, b, x, y; while(~scanf(%d%d, a, b)){ int ret ex_gcd(a, b, x, y); printf(x : %d, y : %d, ret %d\n, x, y, ret);//其实ret就是ab的最大公约数 printf(%d * %d %d * %d %d\n, a, x, b, y, a * x b * y); } return 0; }比如使用程序计算满足100和60的最大公因数20的x,y:贝祖定理的XY是多值的具体看如下分析多值性从程序中可见端倪递归结束条件成立时*x 1;*y 0;其实是表达满足最后一级的两个输入gcd(a,b) 和 0的 x,y可以看到满足gcd(a,b) * x 0 *y gcd(a,b)的解有无数多组只要满足x1, y等于任何值都没有关系。程序中的递归结束条件修改为*y 100;程序仍然能够找到另一组x,y满足 gcd(100,60) * x 0 *y gcd(100,60)程序结论和证明完美统一。GCD的另一个理解无论怎样如果 (a,b)d的话则后续每一部大数减小数与某个整数乘积的步骤得到的结果都是d的倍数并且一定能够取到d的1倍的程度看下图如果最后一步r4kxr5, 如果r5不是1xd, 而是nxd那么根据公式反推回去一定会得到(a,b) nd 而不是(a,b) d所以GCD运算最后一步r5一定是1xdd.完善证明证明过程中依据“每次都保证余数小于除数但是余数不可能小于0由于起始值是有限的所以最终算法一定会停止” 为什么不会出现无限接近0但是不为0的情况算法为什么一定会停止呢a,b可公度这一前提到底保证了什么?可以利用自然数的良序原理(well-ordering principle)说明欧几里得算法一定会终止最小数原理是自然数所具有的一种基本性质即任何非空的自然数集中都有最小的自然数该原理可以推广到整数集有理数集。完整表达是良序原理指出自然数集的每个非空子集都有个最小元素即自然数在其标准的大小关系下构成一良序集。应用-判断链表中存在环路判读链表有环路的快慢指针经典算法的数学基础基于以上讨论算法的逻辑是快慢指针算法是通过两个指针慢指针每次移动一步快指针每次移动两步如果两个指针最终相遇那么链表就存在环。只要慢指针的速度为1快指针的速度可以是任意大于1的值我们可以通过以下数学证明来说明这个算法的正确性假设环链表的长度为O慢指针每次移动1步快指针每次移动s步经过n步后相遇则列出相遇状态的方程为也就是说所以n表示算法进行的步数我们可以取任意自然数表示算法结束时走了多少步为了证明这个算法对任意s都有效我们可以让n O,也就是步数等于链表长度这个时候sk1,也就是说s可以取任意大于1的自然数算法都成立最差最差我在终点等你。2025/03/30 update:前面的证明貌似存在问题确实存在即便存在环路算法仍然检测不出来相遇的情况比如下图环路长度为2快慢节点速度分别为1和3这样每步行动后距离变化2 mod 20也就是距离永远不变永远是初始距离1这样快慢节点永远不会相遇。每次快指针相对于慢指针移动2步设初始距离为d则每步间距变化为 d-(d2)mod 2 d所以如果初始距离d不为0即便链表中存在环快慢指针也不会相遇算法失效。只要初始距离d0从同一个位置出发首次相遇不算在内无论环长多少或者快慢指针速度几何算法总会有效的。最大公因数的性质两个整数的最大公因数确实是所有其他公因数的倍数证明如下根据贝祖定理存在整数x和y使得ax by g。如果另一个因数d是a和b的公因数那么d | ad | b所以d也整除ax by即d | g。因此d | g即存在整数k使得g d * k。这就意味着g是d的倍数也就是g是每个公因数d的倍数。所以结论成立。所以两个整数的最大公因数确实是所有其他公因数的倍数因为每个公因数都能整除最大公因数从而最大公因数就是它们的倍数。且有其中且则证明N表示包括0的自然数集合N*表示排除0的自然数集合。如何计算三个整数a,b,c的的最大公约数要计算三个整数 a、b、cc的最大公约数GCD可以分两步进行利用两次欧几里得算法:GCD(a,b,c)GCD(GCD(a,b),c)贝祖定理的证明参考下面这篇文章https://blog.csdn.net/tugouxp/article/details/146010944?sharetypeblogdetailsharerId146010944sharereferPCsharesourcetugouxpspm1011.2480.3001.8118九章算术中对GCD算法的描述九章算术是中国传统数学的重要教科书其全书问题共分九类有246问和202术汇总了中国先秦至汉朝的数学成就其中就有对GCD算法的描述GCD算法在书中被称为“约分术,其算法描述为月份术曰”可半者半之不可半者副置分母子之数以少减多更相减损求其等也以等数约之“。翻译后是约分算法分子分母都是偶数的可以用2约简否则将分母与分子列在一起然后用大数减去小数将差与上一步的减数再次相减不断重复直到差与减数相等为止这个相等的数字就是他们的最大公约数然后就可以用最大公约数区约简分子和分母了。小时候都做过一类应用题用两种大小的指定杯子装出定量的水这类题在某种情况下无解比如如果两个杯子的最大公因子不能整除要求装出的水量此时无解如果两个杯子互质则可以装出所有整数量的水比如用5L的杯子和6L的杯子装出3L的水的过程如下事实上对于aL和bL杯子装出c L水的问题所有满足 axbyc 的整数解 (x,y)都对应一个可行的用a,b升的桶倒出c升水的方案。参考资料无理数存在性的几何证明-CSDN博客初等数论中整除性规律证明-CSDN博客欧几里得定理的证明-CSDN博客初等数学的整除性规律证明-CSDN博客[深入浅出C语言]理解取整、取余和取模 - 知乎https://zh.wikipedia.org/wiki/%E7%AE%97%E6%9C%AF%E5%9F%BA%E6%9C%AC%E5%AE%9A%E7%90%86结束