• 图解辗转相除法求解最大公约数

    在几何原本卷十命题三中，已知两个可公度的量，计算它们的最大公度量，欧几里得给出了递归解法：

    gcd(a,b)=\left\{\begin{matrix} a \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a = b\\ gcd(a-b, b) \ \ \ b < a\\ gcd(a, b-a)\ \ \ a<b \end{matrix}\right.

    设两条线段a,b可公度，如果它们相等，则最大公度就是其中任意一条线段，此时算法返回a作为结果，如果线段a比b长，就用圆规不断从a中截去b，然后求截端后的线段a'和b的最大公度，如果线段b比a长，就反过来不断从b中截去a,然后求截端后的线段b'和a的最大公度.

    由于a

    gcd(a, b)=\left\{\begin{matrix} a , \ \ \ \ \ \ b=0\\ gcd(b, a\ mod\ b) \end{matrix}\right.

    示意如下：

    程序实现

    gcd（a， b）=  gcd（b， a % b）=  gcd(a%b, b %(a%b)) ....

    先上辗转相除法（欧几里得算法）的三种代码实现：

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. int gcd1(int a, int b)
    5. {
    6.     int ret;
    7.  
    8.     while(1)
    9.     {
    10.         if(a >= b)
    11.         {
    12.             a = a%b;
    13.             if(a == 0)
    14.             {
    15.                 ret = b;
    16.                 break;
    17.             }
    18.         }
    19.         else
    20.         {
    21.             b = b %a;
    22.             if(b == 0)
    23.             {
    24.                 ret = a;
    25.                 break;
    26.             }
    27.         }
    28.     }
    29.  
    30.     return ret;
    31. }
    32.  
    33. int gcd2(int a,int b)
    34. {
    35.     if(b == 0)
    36.         return a;
    37.     return gcd2(b,a%b);
    38. }
    39.  
    40. int gcd3(int a,int b)
    41. {
    42.     while(b){
    43.         int t = b;
    44.         b = a%b;
    45.         a = t;
    46.     }
    47.     return a;
    48. } 
    49.  
    50. int main(void)
    51. {
    52.     int a, b;
    53.     
    54.     a= 100;
    55.     b = 45;
    56.  
    57.     printf("%s line %d, res1 %d, res2 %d, res3 %d.\n", __func__, __LINE__, gcd1(a, b), gcd2(a, b), gcd3(a, b));
    58.  
    59.     return 0;
    60. }

    下面用一幅图示解题过程，图中蓝色的矩形单元表示一个最小公约的单元。它具有以下性质：

    1.以最小公约表示的两个原数字互质。（这是必然，反证法，如果不互质，则可以提取一个共同的因子重新定义最小公约单元，直到表示为互质，比如图中的8和3互质）。

    2.辗转相除的每个阶段的两个数字也均互质，证明过程类似，反正法即可（当前辗转阶段如果存在共同的约数，则必然传递到之前的阶段也都有同样的约数，所以同理最小公约单元也要重新定义，直到每级辗转互质）。

    基于以上两个严密的逻辑，辗转相除一定能够找到组成两个数字的最基本的公约块儿，它是两个数字共有的零件。

    扩展-求最小公倍数

    既然上一步已经计算得到了最小公约数，并且得到了以最小公约表示的两个原数字互质的推论，就不难得到计算最小公倍数的公用公式。

    通用算法，已知数字m,n的最大公约数是g,则m/g, n/g互质，两个互质的数的最小公倍数就是两个质数之积，所以，最小公倍数为

    \frac{m}{g}\cdot \frac{n}{g} = \frac{mn}{g^2}

    由于单元为g,所以最小公倍数的真实值为：

    \frac{m}{g}\cdot \frac{n}{g}\cdot g = \frac{mn}{g^2}\cdot g = \frac{mn}{g}

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. int gcd1(int a, int b)
    5. {
    6.     int ret;
    7.  
    8.     while(1)
    9.     {
    10.         if(a >= b)
    11.         {
    12.             a = a%b;
    13.             if(a == 0)
    14.             {
    15.                 ret = b;
    16.                 break;
    17.             }
    18.         }
    19.         else
    20.         {
    21.             b = b %a;
    22.             if(b == 0)
    23.             {
    24.                 ret = a;
    25.                 break;
    26.             }
    27.         }
    28.     }
    29.  
    30.     return ret;
    31. }
    32.  
    33. int gcd2(int a,int b)
    34. {
    35.     if(b == 0)
    36.         return a;
    37.     return gcd2(b,a%b);
    38. }
    39.  
    40. int gcd3(int a,int b)
    41. {
    42.     while(b){
    43.         int t = b;
    44.         b = a%b;
    45.         a = t;
    46.     }
    47.     return a;
    48. } 
    49.  
    50. int lcm1(int a, int b)
    51. {
    52. 	int g_c_d = gcd1(a, b);
    53.  
    54. 	return a*b/g_c_d;
    55. }
    56.  
    57. int lcm2(int m, int n)
    58. {
    59. 	int mn, r ;
    60. 	
    61. 	if(m<n){
    62. 		mn = m ; 
    63. 		m = n ; 
    64. 		n = mn;
    65. 	}
    66. 	
    67. 	mn = m * n ;//俩个数的乘积
    68. 	r = m % n ;
    69. 	while(r!=0){
    70. 		m = n ;
    71. 		n = r ;
    72. 		r = m % n ;
    73. 	}
    74. 	return mn/n; //n为最大公约数
    75. }
    76.  
    77. int main(void)
    78. {
    79.     int a, b;
    80.     
    81.     a= 100;
    82.     b = 45;
    83.  
    84.     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));
    85.  
    86.     return 0;
    87. }
    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.

    不失一般情况，假设a

    \frac{ka}{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互质,则设m=ab,ab为m的一个质因数分解.根据算数基本定理,这个指因数分解唯一.如果存在c=ab/n=m/n,则必然存在m=cn,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,使得ax+by=1,等式两边同时乘以c，得到acx+bcy=c.

    由于bc能够整除a，所以a*cx+bc*y实际上是两个能够整除a的整数的线性组合（cx,y为系数），所以a*cx+bc*y也能够整除a. 而a*cx+bc*y等于什么呢？它就等于c，所以a|c. 结论得到证明。

    或者通过欧几里德定理证明，素数的唯一分解角度：

    (a,b)=1.且a|bc，如果将a,b,c三个数字进行欧几里德素数分解，则a,b互素，所以它们一定没有除1以外的共因子。 因此c必须包含所有a的素因子，并且唯一，因此a一定能够整除c.

    总结：

    基本原理：两个整数的最大公约数等于，其中较小的数和两数的差的最大公约数。

    个人解析：若A、B有最大公约数K（A > B)，则，A、B、（A - B）、A mod B（A / B的余数），都是K的倍数。即余数（A - B）和 B 的最大公公约数也是 K 。

    由此递归，可知当 A mod B = 0，即 A 是 B 的倍数时，此时，B 即为 K 。实际上，存在如下定理：

    两数最大公约数与最小公倍数的积等于两数之积，用公式表示就是：

    gcd(p,q)\times lcm(p,q)=pq

    当

    gcd(p,q)=1

    时

    lcm(p,q)=pq

    最大公因数*最小公倍数=pq。

    这个证明过程也很简单，假设a,b互质，那么它们的最小公倍数是ab,最大公因数1，满足题设。

    假如a,b不互质，则必然存在质数 p,q， (p,q)=1,s=gcd(a,b),使的a = sp,b=sq, s为整数。则最小公倍数为spq,最大公约数为s.同样满足题设。

    这个证明需要的引理(p,q)=1，则lcm=pq，可以根据算数基本定理证明，(p,q)=1说明,p,q的素分解式中不存在相同的素数，否则，他们的(p,q)=1必定不成立（要么某个相同的素数，要么某几个相同的素数之积），所以，他们的lcm一定是所有p,q的素因子之积，而素因子又不存在交集，所以lcm一定是pxq.

    图形化表示辗转相除获取最大公约数

    证明: gcd(a,b) = gcd(b, a%b).

    设c=gcd(a,b). 则：

    a = mc

    b = nc 

    并且m,n互素（假如m,n有公因子，则一定可以抽取出来和c作乘积产生新的最大公约数，而前提我们已经设定c为最大公约了，所以一定有办法让m,n互素).

    a=qb+r=>mc=qnc+r =>r=mc-qnc = (m-qn)c.

    所以c仍然是a%b的因子。

    又因为m-qn和n互素（证明如下，假如m-qn和n有非1公因子s,gcd(n, m-qn) = s, n=xs, m-qn=ys.

    则，r=(m-qn)c = ysc, a=qxsc+ysc, b = xsc.所以a,b的公因子是少是sc而非c. 或者这样理解：

    m-qn=x*s, n=y*s=>m=(qy+x)s,所以，m,n有公因子s，和m,n互素矛盾，所以m-qn和n互素）。

    所以，b=nc和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, 并且a>b，b非0，可以证明存在两个唯一的整数 q 和 r，满足 a = q*b + r , q 为整数，且0 ≤ |r|< |d|。其中，q 被称为商，r 被称为余数，a,b分别被除数和除数，取余运算求取的就是这个余数r。

    a=q_0b+r_0

    b=q_1r_0+r_1

    r_0=q_2r_1+r_2

    r_1=q_3r_2+r_3

    r_2=q_4r_3+r_4

    r_3=q_5r_4+r_5

    .........

    r_{n-2}=q_{n}r_{n-1}+r_{n}

    r_{n-1}=q_{n+1}r_{n}+r_{n+1}

    r_n=q_{n+2}r_{n+1}+r_{n+2}

    \mathbf{\textbf{}r_{n+1}=q_{n+3}r_{n+2}}

    只要a,b是可公度的，这些式子不会无限列下去，从r0开始，每一步r(n+1)是r(n)的余数，r(n+1) < r(n),但是r0是自然数，起始值是有限的，所以这个过程不可能无限进行下去，最后一步总归能够整除，最后一步的除数r(n+2)就是最大公约数。

    b > r_0>r_1>r_2>\cdots>r_{n+2}>0

    往回迭代：

    r_n=q_{n+2}(q_{n+3}r_{n+2})+r_{n+2}

    r_{n-1}=q_{n+1}q_{n+2}q_{n+3}r_{n+2}+q_{n+1}r_{n+2}+q_{n+3}r_{n+2}

    \boldsymbol{r_{n-2}=q_nq_{n+1}q_{n+2}q_{n+3}r_{n+2}+q_nq_{n+1}r_{n+2}+q_nq_{n+3}r_{n+2}+q_{n+2}q_{n+3}r_{n+2}+r_{n+2}}

    .........

    b=q_1q_2...q_{n+3}r_{n+2} + ....(......+ ......)r_{n+2}

    a=q_0q_1q_2...q_{n+3}r_{n+2} + ....(......+ ......)r_{n+2}

    下一步证明，任何a,b的公度c,一定可以度量r(n+2).

    由于c是公度，因此a,b都可以用它来表示，m,n为自然数

    a=mc, b=nc

    这样，上面的式子可以写成

    a=q_0b+r_0

    b=q_1r_0+r_1

    mc=q_0nc+r_0

    nc=q_1(m-nq_0)c+r_1

    r_0=(m-nq_0)c

    r_1=(n-q_1m+q_1q_0n)c

    .....

    所以，r0,r1,.....r(n),r(n+1), r(n+2)都可以由c来公度，所以r(n+2)是最大公度。

    以本片开头的例子为例，计算110和24的最大公约数，a=110,b=24.

    a=110,b=24.

    110=4*24+14.

    24=1*14+10.

    14=1*10+4.

    10=2*4+2.

    4=2*2 + 0.

    定理得证。

    裴蜀定理

    裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a ,b 和它们的最大公约数d,关于未知数x和y 的线性不定方程（称为裴蜀等式):若a ,b 是整数,且gcd(a,b)=d,那么对于任意的整数x ,y , ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立,对于a,b互素的情况，一定存在x,y使的ax+by=1.

    可以这样抽象理解，每次a mod b=m余r的过程，都是：

    a-m_kb = r_k \\ \boldsymbol{b-m_{k+1}r_k=r_{k+1} = b-m_{k+1}(a-m_kb)=(1+m_{k+1}m_k)b-m_{k+1}a=r_{k+1}}

    所以：

    r_{k+1}=ax_{k+1}+by_{k+1}

    r_{k+2}=ax_{k+2}+by_{k+2}

    r_{k+3}=ax_{k+3}+by_{k+3}

    .......

    也就是说，通过GCD计算最大公约数的过程，就是计算a,b线性组合的过程，系数分别为x,y：r=ax+by.

    计算gcd(a,b)=ax+by所需的x,y:

    a=q_0b+r_0, \ q_0=\frac{a}{b}

    b=q_1r_0+r_1,\ q_1=\frac{b}{r_0}

    ......

    方程是不定方程，无法限定x,y.符合要求的x,y可以构成一个一维空间，在一条直线上，但是满足x,y为整数的，并不多。另外，对于ax+by=k形式的直线，如果a,b互质，则K可以为任意整数，但是如果a,b的最小公因数大于1，则小于其最公因数的数字不能被表示。可以简单证明如下：

    ax+by=k, a=nc, b=mc. 则ncx+mcy=k=>c(nx+my)=k,n,m互质，所以能表示任意整数。

    ((m,n)=1,则存在 mx+by=1,两边同时乘以任意整数，则可以表示任意数）

    在乘以一个c，则只能表示sc了,s是整数。不能表示任意整数了。

    假设第k层：

    p_kx_k+q_ky_k=1

    第k+1层:

    p_{k+1}x_{k+1}+q_{k+1}y_{k+1}=1

    p_{k+1}=q_{k}

    q_{k+1}=p_k \% q_k

    所以：

    q_kx_{k+1}+(p_k-mq_k)y_{k+1}=1, m=\frac{p_k}{q_k}

    展开:

    q_kx_{k+1}+p_ky_{k+1}-mq_ky_{k+1}=1, m=\frac{p_k}{q_k} \\ q_k(x_{k+1}-my_{k+1})+p_ky_{k+1}=1, m=\frac{p_k}{q_k}

    对照第K层：

    p_kx_k+q_ky_k=1

    所以

    x_k=y_{k+1} \\ y_k=x_{k+1}-my_{k+1} \\ m=\frac{p_k}{q_k}

    并且，在最后一次的迭代中，一定是

    p_k = 1, q_k = 0,x_k = 1, y_k=0,编程得到：

    1. #include<stdio.h>
    2. #include<stdlib.h>
    3.  
    4. //注意，a，b必须互质！
    5. int ex_gcd(int a, int b, int *x, int *y) 
    6. {    
    7.     int x1, y1, r;
    8.  
    9.     if(b == 0) {
    10.         if(a!= 1) {
    11.             printf("%s line %d, error, a %d is not 1 in last recursive.\n", 
    12.                 __func__, __LINE__, a);
    13.             exit(-1);
    14.         }
    15.  
    16.         *x = 1;
    17.         *y = 0;
    18.         return a;
    19.     }
    20.  
    21.     r = ex_gcd(b, a % b, &x1, &y1);
    22.     *y = x1 - a / b * y1;          //根据推导的每层x，y的关系而来
    23.     *x = y1;                       //同上
    25.     return r;
    26. }
    27.  
    28. int main(void)
    29. { 
    30.     int a, b, x, y;
    31.  
    32.     while(~scanf("%d%d", &a, &b)){
    33.         int ret = ex_gcd(a, b, &x, &y);
    34.         printf("x : %d, y : %d, ret = %d\n", x, y, ret);//其实ret就是a，b的最大公约数
    35.         printf("%d * %d + %d * %d = %d\n", a, x, b, y, a * x + b * y);
    36.     }
    37.  
    38.     return 0;
    39. }

    下图展示了两个整数6和9的最大共因子是两个整数的线性组合的最小正整数这个事实：

    GCD的另一个理解

    无论怎样如果 (a,b)=d的话，则后续每一部大数减小数与某个整数乘积的步骤，得到的结果都是d的倍数，并且一定能够取到d的1倍的程度，看下图，如果最后一步r4=kxr5, 如果r5不是1xd, 而是nxd，那么根据公式反推回去，一定会得到(a,b) =nd 而不是(a,b) =d，所以GCD运算最后一步r5一定是1xd=d.

    完善证明

    证明过程中，依据“每次都保证余数小于除数，但是余数不可能小于0，由于起始值是有限的，所以最终算法一定会停止” 为什么不会出现无限接近0但是不为0的情况，算法为什么一定会停止呢？a,b可公度这一前提到底保证了什么?

    可以利用自然数的良序原理(well-ordering principle)说明欧几里得算法一定会终止，最小数原理是自然数所具有的一种基本性质，即任何非空的自然数集中都有最小的自然数，该原理可以推广到整数集，有理数集。完整表达是：

    良序原理指出，自然数集的每个非空子集都有个最小元素，即自然数在其标准的大小关系下构成一良序集。

    参考资料

    无理数存在性的几何证明-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

    结束

  • 相关阅读:
    SQL每日一练（牛客新题库）——第6天：必会常用函数
    Asp-Net-Core学习笔记：3.使用SignalR实时通信框架开发聊天室
    第六十二章 符号概览
    python小知识
    Java 开源开发平台 O2OA V7.2.0 发布，新增系统配置图形化模块和企业文件模块！
    110、数据转换的事情，谁来做？
    大学生简单静态HTML网页模板源码——家乡介绍美丽乡村11页
    Flutter | bloc 之 state 使用优化
    链上信使协议AMOP
    Route53 – Part 2
  • 原文地址：https://blog.csdn.net/tugouxp/article/details/126820935