中国余数定理

「爱情、让人受尽委屈。」 2022-08-13 13:43 242阅读 0赞

我国古代数学名著《孙子算经》载有一道数学问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”这里的几何指多少的意思。翻译成数学语言就是：求正整数N，使N除以3余2，除以5余3，除以7余2。

建立数学原型：  
已知m1、m2、m3是两两互质的正整数，求最小正整数x，使它被m1、m2、m3除所得余数分别为C1、C2、C3 。  
列成同余式子：

x≡a1 (mod m1)(表示x除以m1和a1除以m1的余数一样，下面一样)

x≡a2 (mod m2)，

x≡a3 (mod m3)，

对于孙子算经中的例子也就是，

x≡2 (mod 3)

x≡3 (mod 5)，

x≡2 (mod 7)，

现在需要求解这个x。

求解方程组需要下列步骤：

(1) 求M=m1 X m2 X m3 X ... X mK，这是普通的模;

(2) 求M1 = M/m1, M2 = M/m2, ... , Mk =M/mk;

(3) 求M1, M2, ..., Mk在模m1, m2, ..., mk的乘法逆[![184009705.jpg][]][184009705.jpg 1] ;

(4) 方程组的解是，[![184047670.jpg][]][184047670.jpg 1]。

那什么是乘法的逆呢？也就是乘法逆元。

若ax ≡1 (mod f )，责称a对f的逆为x 只有a与f互素时，a关于模f的乘法逆元有唯一解。如果不互素，则无解。

下面开始求解方程组：

(1) M = 3 X 5 X 7 = 105

(2)[![184141703.jpg][]][184141703.jpg 1]

(3) 根据上面的求逆公式： 35 X 2  mod 3 = 1, 21 X 1 mod 5 = 1, 15 X 1 mod 7 = 1,所以M1、M2、M3的逆为：[![184206911.jpg][]][184206911.jpg 1]

在实际写算法时，我们可以通过扩展欧几里德算法去求解逆元。

因为ax mod f = 1, x为a模f的逆元，假设此时的商为y，有：

ax = fy + 1 -----> ax-fy = 1,明显的扩展欧几里德算法的模型。

(4) [ ![184241886.jpg][]][_184241886.jpg]

这个满足条件的x就是 23.

参考文档：

[http://shuxueshi.jie.blog.163.com/blog/static/13611628820104179856631/][http_shuxueshi.jie.blog.163.com_blog_static_13611628820104179856631]

[http://book.51cto.com/art/200812/102579.htm][http_book.51cto.com_art_200812_102579.htm]

[  
][http_book.51cto.com_art_200812_102579.htm]

当时我们的算法老师还出了个中国余数定理的算法题：

实现中国余数定理算法并求满足下列条件的x?

(1)x mod 97=26       (2)x mod 32=17

具体的解决方法也是按照上面的方法,这是求解两个数，但扩展到多个数也是一样的。

写成c语言代码解决如下：

#include<stdio.h>
    
    int count(int a, int b)
    {
    	return a / b;
    }
    
    int extendedGcd(int a, int b, int * x, int * y)
    {
        int r;   //最大公约数
        int temp;  
        if (b == 0)
        {
            *x = 1;
            *y = 0;
            return a;    //a是最大公约数
        }
        r = extendedGcd(b, a % b, x, y);  //x和y是一个指针
        //x1 = y2, y1 = x2 - (a / b) * y2 
        
        temp = *x;
        *x = *y;
        *y = temp - (a / b) * (*y);
        return r;     //返回最大公约数
    }
    
    int main()
    {
    	/*求正整数N, 使N除以97余26,除以32余17*/
    	int m1 = 97, m2 = 32;   //除数
    	int a1 = 26, a2 = 17;   //余数
    	int M = m1 * m2;  
    	
    	int M1 = count(M, m1);	
    	int M2 = count(M, m2);
    	
    	int x1, y1; //通过扩展欧几里德算法求逆元，x1是M1模m1的逆
    	int x2, y2;    //x2是M2模m2的逆
    	extendedGcd(M1, m1, &x1, &y1);    //求M1的逆
    	extendedGcd(M2, m2, &x2, &y2);    //求M2的逆 
    	
    	int num;   //满足要求的x
    	num = (a1 * M1 * x1 + a2 * M2 * x2) % M;
    	printf("所求的数字为: %d\n", num + M);    //求得的num是一个负数，但这不影响我们所要求的数字，加上97和32的最小公倍数M即可
    	
    	return 0;
    }

[184009705.jpg]: /images/20220810/ef5e32befa624cd0a6a04f8085fa33ad.png
[184009705.jpg 1]: http://new.51cto.com/files/uploadimg/20081222/184009705.jpg
[184047670.jpg]: /images/20220810/a691e62b13c541188e9c45ec21c9ee9c.png
[184047670.jpg 1]: http://new.51cto.com/files/uploadimg/20081222/184047670.jpg
[184141703.jpg]: /images/20220810/ea3a2540fa254f2da05cd77555220949.png
[184141703.jpg 1]: http://new.51cto.com/files/uploadimg/20081222/184141703.jpg
[184206911.jpg]: /images/20220810/f81ec063141f41b2929687a05a9237b7.png
[184206911.jpg 1]: http://new.51cto.com/files/uploadimg/20081222/184206911.jpg
[184241886.jpg]: /images/20220810/46ed384c30104138b160b26e08405545.png
[_184241886.jpg]: http://new.51cto.com/files/uploadimg/20081222/184241886.jpg
[http_shuxueshi.jie.blog.163.com_blog_static_13611628820104179856631]: http://shuxueshi.jie.blog.163.com/blog/static/13611628820104179856631/
[http_book.51cto.com_art_200812_102579.htm]: http://book.51cto.com/art/200812/102579.htm