孙子定理课件(07版)

中国剩余定理（孙子定理）问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。

问物几何？简单点说就是，存在一个数x，除以3余2，除以5余三，除以7余二，然后求这个数。

上面给出了解法。

再明白这个解法的原理之前，需要先知道一下两个定理。

定理1：几个数相加，如果存在一个加数，不能被整数a整除，那么它们的和，就不能被整数a整除。

定理2：两数不能整除，若除数扩大（或缩小）了几倍，而被除数不变，则其商和余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。

以上两个定理随便个例子即可证明！现给出求解该问题的具体步骤：1、求出最小公倍数lcm=3*5*7=1052、求各个数所对应的基础数（1）105÷3=3535÷3=11......2 //基础数35（2）105÷5=2121÷5=4 (1)定理2把1扩大3倍得到3，那么被除数也扩大3倍，得到21*3=63//基础数633、105÷7=1515÷7=2 (1)定理2把1扩大2倍得到2，那么被除数也扩大2倍，得到15*2=30//基础数30把得到的基础数加和（注意：基础数不一定就是正数）35+63+30=1284、减去最小公倍数lcm（在比最小公倍数大的情况下）x=128-105=23那么满足题意得最小的数就是23了。

一共有四个步骤。

下面详细解释每一步的原因。

（1）最小公倍数就不解释了，跳过（记住，这里讨论的都是两两互质的情况）（2）观察求每个数对应的基础数时候的步骤，比如第一个。

105÷3=35。

显然这个35是除了当前这个数不能整除以外都能够被其他数整除，就是其他数的最小公倍数。

相当于找到了最小的起始值，用它去除以3发现正好余2。

那么这个基础数就是35。

记住35的特征，可以整除其他数但是不能被3整除，并且余数是2。

体现的还不够明显，再看下5对应的基础数。

21是其他数的最小公倍数，但是不能被5整除，用21除以5得到的余数是1，而要求的数除以5应该是余1的。

中国余数定理通常指的是“孙子定理”。

孙子定理是解决中国古代全等系统的一种方法。

它是数论中的重要定理。

也称为中文余数定理。

一个变量的线性同余方程组的问题可以在《孙子算经》第二卷的第二十六个问题中找到。

这是中国南北朝（公元5世纪）的数学著作。

“这个事不知道人数”有些东西不知道其编号。

三分之二，五分之三和七分之二。

物质的几何形状是什么？也就是说，一个整数除以3加2，再除以5等于3，再除以7加2。

孙子算经中首先提到了同余方程的问题和上述特定问题的解决方案。

因此，中国余数定理在中国数学文献中也称为“孙子定理”。

一个变量的线性同余方程组的问题可以在《孙子算经》第二卷的第二十六个问题中找到。

这是中国南北朝（公元5世纪）的数学著作。

“这个事不知道人数”有些东西不知道其编号。

三分之二，五分之三和七分之二。

物质的几何形状是什么？也就是说，一个整数除以3加2，再除以5等于3，再除以7加2。

孙子算经中首先提到了同余方程的问题和上述特定问题的解决方案。

因此，中国余数定理在中国数学文献中也称为“孙子定理”。

1247年，宋代数学家秦久少针对《书九掌》第一卷和第二卷中的“物不知数字”问题给出了完整而系统的解决方案。

明代数学家程大为将解决方案汇编成孙子的引人入胜的公式三人一起旅行70棵罕见的二十一棵梅树，七个孩子团聚半个月，只有一百零五名使节知道当模数为3、5、7时，这首韵给出了秦久绍等价方程的解。

这意味着：将余数除以3除以70，除以5除以21，除以7除以15，再除以105（或105的倍数）得到答案。

例如，在上面的未知数问题中，根据公式，结果为23。

孫子定理中國人在世界數學史上的偉大成就之一――――孫子定理孫子算經是我國古代的一本優良數學書籍，作者與年代不詳成書約在西元270年至743年間魏晉南北時期，分成上、中、下三卷，上卷敘述籌算的乘除法，中卷敘述籌算的分數算法與開方法，是了解中國古代籌算很好的資料，下卷收集了一些算術難題，如「雞兔同籠」，最有名的要算下卷第26題，通常所稱的「孫子問題」或「物不知其數」，孫子問題不僅是一個有趣的算術問題，而且和中國古代曆法的推算有很密切關係。

孫子問題在中國民間流傳很廣，有「韓信點兵」，「秦王暗點兵」等名稱，其解法也有不同名稱，宋周密稱為「鬼谷算」，「隔牆算」，楊輝稱為「剪管術」秦九韶在其所著「數書九章」（西元1247年）稱為「大衍求一術」等，孫子問題的算法，英國數學家Alexander Wylie（1815-1887）經由其著作中國算學叢談一書介紹到西方，稱為「中國剩餘定理」。

歐洲直到18-19世紀，尤拉（Euler，1707-1789）與高斯（Gauss，1777-1855）等人才對此類問題進行研究。

比秦九韶等人晚了四、五百年。

孫子問題這類問題的解法屬於數學的一個分支――數論，在近代數學仍占有重要地位。

方法與原則，反映在插入理論、代數理論及算子理論，在計算機的設計中也有重要應用。

介紹孫子問題時，先玩一個遊戲遊戲:「有位魔「數」師，聲稱在1000之內任選一整數，只要告訴魔「數」師，此數除以7、11、13，所得的餘數r1、r2、r3，就能猜出你所選的數。

如此數除以7、11、13，所得餘數分別為1、2、3 ，則此數為211。

你知道魔「數」師是如何得知的嗎? 」答：5(11×13)r1+4(7×13)r2+12(7×11)r3-α(7×11×13)= 5(143)r1+4(91)r2+12(77)r3- )(1001韓信點兵「三人一列，則餘1人，五人一列，則餘2人，七人一列，則餘4人，十三人一列，則餘6人，問兵至少多少人?」答：2(5×7×13)r1+2(3×7×13)r2+6(3×5×13)r3+(3×5×7)r4-α(3×5×7×13)=2(455)r1+2(273)r2+6(195)r3+(105)r4-α(1365)至少487+α(1365)孫子算經中的孫子問題「物不知其數，三三數之賸二，五五數之賸三，七七數之賸二，問物幾何?」答曰：二十三術曰：三三數之賸二，則置一百四十，五五數之賸三，則置六十三，七七數之賸二，則置三十，并之得二百三十三，以二百一十減之即得。

《孙子定理》及对它的推广我国古代数学名著《孙子算经》中记有“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” 这就是千百年来在数学界甚至在民间广泛流传的“物不知数”问题，也称为“孙子问题”。

该问题书中不但给出了答案，并且记述了解法，其解法经历代中国数学家的研究推广，就形成了通常所说的《孙子定理》（外国称中国剩余定理）。

此定理用现代数学语言叙述，一般都用数论中的同余理论，但从研究的问题类型上看，用“带余除法算式”（指：被除数=除数×商数+余数）表述更为自然易懂，因此，《孙子定理》也可叙述为：设m 1,m 2,...,m k 是k 个两两互质的正整数（k ≥2）;b 1,b 2,...,b k , 为任意整数，得方程组：显然，应用《孙子定理》关键是先要求出F i 的值，由（2）式x=m 1y 1+b 1x=m 2y 2+b … x=m k y k +b k 取M==Ki 1i 整数F i 满足：F i M i =m i q i +1（q i 为整数），i=1，2,...k (2)如果i i Ki i b M F ∑=1=Mq+r （q,r 均为整数，0＜r ＜M ），则方程组（1）的解 x=r+nM （n 取任意整数）可知，因M i与m i互质，根据两数最大公约数的性质可知，存在整数F i和q i满足（2）式，并且能求出这两个值（在应用定理时只需要F i的值）求（2）式中F i的值一般情况可以分两步：1.首先利用辗转相除的思路对（2）式中M i与m i辗转相除，因M i与m i互质故必有余数是+1或-1。

2.当得到余数+1或-1时，再由辗转相除的等式，结合（2）是求出F i的值。

例如，求整数F满足：〈1〉19F=7q+1, 〈2〉3F=11q+1解：〈1〉对19与7辗转相除；因为19=7×2＋5(第一个余数是5)7=5×1+2(第二个余数是2)5=2×2+1(第三个余数是1)所以，1=5-2×2=5-(7-5×1)×2=5×3–7×2=(19–7×2)×3–7×2=19×3–7×8即: 19×3=7×8+1故，F=3〈2〉因为11=3×4–1(余数是-1)所以3×4=11×1+1故F=4注意:对（2)式中M i与m i辗转相除，当第一个余数不是(+1)或(-1)时，可先将(2)化为与其等价的(M i-m i t)F i=m i Ri+1式中t取适当整数，使得（M i-m i t）的绝对值与m i辗转相除尽快得到余数是（+1）或(-1)。

“物不知数”——孙子定理有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二.问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数.《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理.孙子问题的解法，以现代的说法，是找出三个关键数70，21，15。

解法的意思就是用70乘3除所得的余数，21乘5除所得的余数，15乘7除所得的余数，然後总加起来，除以105的余数就是答案。

即题目的答案为：70×2+21×3+15×2=140+63+30=233233-2×105=23公式：70a+21b+15c-105n关键是找出70 21 15宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答.明朝数学家程大位将解法编成易于上口的《孙子歌诀》：三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法.意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后减去105（或者105的倍数），得到的余数就是答案.比如说在以上的物不知数问题里面，按歌诀求出的结果就是23.又例今有一类数，除以3余数是2，除以5余数是3，除以7余数是4.试问这类数中最小的正整数是多少？35+63+60-105=5353第一步：在 5,7的公倍数中找出“除以3余数是2”的数；35第二步：在 3,7的公倍数中找出“除以5余数是3”的数；21,42, 63第三步：在 3,5的公倍数中找出“除以7余数是4”的数，15,30,45, 6035+63+60=158,158肯定是符合“除以3余数是2，除以5余数是3，除以7余数是4”的，但不一定最小，去掉若干个3,5,7的最小公倍数，使之变成最小的正整数。

孙子定理余数定理孙子定理是一个在数学中很有用的定理,它用来解决一类类似于 "每个人都和另一个人配对,每对之间的差是一个固定数值" 的问题。

具体来说,假设有 $n$ 个人,他们的年龄分别是 $a_1,a_2, \dots, a_n$,每个人都和另一个人配对,每对之间的差是 $d$。

那么,孙子定理告诉我们,当 $n$ 为偶数时,必定存在一组配对方案使得每对之间的差都是 $d$。

举个例子,假设有四个人,他们的年龄分别是 20、25、30、35,每对之间的差是 5。

那么,这四个人可以这样配对：20 和25,30 和 35。

这样就满足了每对之间的差都是 5。

孙子定理的证明需要用到一种叫做 "余数定理" 的结论。

余数定理告诉我们,对于任意两个自然数 $a$ 和 $b$,必定存在整数 $x$ 和 $y$,使得 $a \times x + b \times y = \gcd(a, b)$。

这个余数定理可以用来证明孙子定理。

假设我们要证明孙子定理,即对于给定的 $n$ 个自然数 $a_1, a_2, \dots, a_n$ 和 $d$,当 $n$ 为偶数时,必定存在一组配对方案使得每对之间的差都是 $d$。

首先,我们可以设 $b = nd$,由余数定理可知,对于任意的自然数 $b$,都有 $\gcd(b, n) \mid b$。

因此,对于给定的$b = nd$,有 $\gcd(b, n) \mid nd$。

接下来,我们考虑对 $n$ 个数中的任意两个数 $a_i$ 和$a_j$（$i \neq j$）,它们的差是 $a_i - a_j = d$。

因此,有 $\gcd(a_i - a_j, n) \mid d$。

根据余数定理的结论,我们可以继续证明孙子定理。

对于给定的 $n$ 个数 $a_1, a_2, \dots, a_n$ 和 $d$,假设 $\gcd(a_i - a_j, n) = k$,那么根据余数定理,有 $k \mid a_i - a_j$。

中国剩余定理（孙⼦定理） 中国剩余定理，也叫孙⼦定理，是数论中的⼜⼀个重要定理，那么它是⼲什么⽤的呢？简单来说，这是⼀个⽤来求⼀元线性同余⽅程组的定理。

叫做孙⼦定理的原因就是该定理最早可见于南北朝时期的著作《孙⼦算经》卷下第⼆⼗六题，叫做“物不知数”问题，原⽂如下： 有物不知其数，三三数之剩⼆，五五数之剩三，七七数之剩⼆。

问物⼏何？ 翻译⼀下，就是说，⼀个数除以三余⼆，除以五余三，除以七余⼆，求这个整数。

接下来，我们把这⼀道题作为例题，探究⼀下如何利⽤孙⼦定理搞定同余⽅程组例1： 求解⼀元线性同余⽅程组： x ≡ 2 ( mod 3 ) x ≡ 3 ( mod 5 ) x ≡ 2 ( mod 7 ) 解： 做题依据： 当p1 , p2 , ……互质的时候，有 x ≡（a1 q1 q1-1+ a2 q2 q2-1+……）mod P 其中P = p1 p2……， q i = p / p i ，q i-1为 q i 在模p i 意义下的逆元 对于这道题，x ≡（2 * 35 * 2 + 3 * 21 * 1+ 2 * 15 * 1）mod 105 = 23例2： 求解⼀元线性同余⽅程组： x ≡ 3（mod 12） x ≡ 2（mod 18） 解： 做题依据 当p不互质时，有x ≡ a1 ( mod p1 ) = = > x = a1 + p1 b1, x ≡ a2 ( mod p2 ) = = > x = a2 + p2 b2 所以p1 b1 - p2 b2 = a2 - a1 ⽤扩展欧⼏⾥得得解 因此不断合并⽅程即可2019-04-09 11:39:10。

《孙子定理》诌议我国古代数学名著《孙子算经》中记有：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三。

”书中不但给出了答案，而且提供了解法。

此类问题，后经历代中国数学家研究推广，就形成了通常所说的《孙子定理》（外国称中国剩余定理）。

此定理用现代数学符号表述一般都用初等数论中的同余概念，但从定理的具体内容用“带余除法”（指：被除数=除数×不定商+余数）的形式叙述更为自然易懂。

因此，该定理可表述为：某数x，用m1除余b1，用m2除余b2，…，用m k除余b k，即（1）m1, m2, …, m k是k个两个互质的正整数（k≥2），M=m1m2…m k，，，…，，（0<r<M）（2）则方程（1）的解，（k取任意整数）。

其中：，（i=1,2,…,k）（3）由（2）式可知，应用《孙子定理》的关键是求出F i(i=1,2,…k)的值。

那么怎样求出F i的值呢？因为（3）式可化为：（4）由于m1,m2,…,m k两两互质可知M i与m i也互质，故它们的最大公约数是（1），根据两数最大公约数的性质，存在F i（和q i）使得（4）式成立。

为此，先用辗转相除法求出（4）式也就是（3）式中M i与m i的最大公约数。

对M i与m i辗转相除是指下列一串等式：当r n=1（这就是M i与m i的最大公约数）时，再利用这串等式求得F i的值。

例如，设（3）式中M i=7，m i=5 则7F i=5q i+1。

首先对7与5辗转相除，求它们的最大公约数（1）。

，（这里r2=1，是7与5的最大公约数）利用上式求F i的值：即，故得F2=-2。

我们可以证明，用上述方法求（3）式中F i的值，如F i=F0，则F0+Km i（K取任意整数）都是F i的值。

本例F i=-2，那么-2+5K（K取任意整数）都满足7F i=5q i+1，但在应用《孙子定理》中只需要求出一个值即可。

孙子定理公式详解孙子定理，也称为中国剩余定理，是数论中的一个重要定理。

这定理听起来是不是有点高大上，让人感觉摸不着头脑？别担心，咱一步步来把它弄明白。

先来说说孙子定理到底是个啥。

想象一下，你有一堆苹果，要分给几个小伙伴。

但是呢，你只知道这些苹果除以某个数会余几，除以另一个数又会余几，然后你想知道到底有多少个苹果。

这时候孙子定理就派上用场啦！比如说，有一堆物品，除以 3 余 2，除以 5 余 3，除以 7 余 2，那这堆物品最少有多少个？这就是孙子定理能解决的问题。

咱们来看看孙子定理的公式。

假设整数 m1，m2，... ，mk 两两互质，M = m1 × m2 ×... × mk，Mi = M / mi（i = 1，2，... ，k），则同余方程组：x ≡ a1（mod m1）x ≡ a2（mod m2）...x ≡ ak（mod mk）的解为：x = （a1M1y1 + a2M2y2 +... + akMkyk）mod M ，其中 yi满足Miyi ≡ 1 （mod mi）（i = 1，2，... ，k）。

哎呀，这公式是不是看起来有点复杂？别着急，咱们通过一个具体的例子来理解。

就拿前面说的那堆物品的例子，除以 3 余 2，除以 5 余 3，除以 7余 2。

首先，3、5、7 两两互质，M = 3×5×7 = 105。

M1 = 105÷3 = 35，M2 = 105÷5 = 21，M3 = 105÷7 = 15。

接下来要找 y1、y2、y3，使得35y1 ≡ 1 （mod 3），21y2 ≡ 1（mod 5），15y3 ≡ 1 （mod 7）。

对于35y1 ≡ 1 （mod 3），因为 35 = 3×11 + 2，2×2 ≡ 1 （mod 3），所以 y1 = 2。

对于21y2 ≡ 1 （mod 5），因为 21 = 5×4 + 1，所以 y2 = 1。

孙子定理过程嘿，咱今儿个就来唠唠这神奇的孙子定理！你说这孙子定理啊，就像是一把解开难题的钥匙。

想象一下，你面前有一堆杂乱无章的数字，就像一团乱麻，让你头疼不已。

可孙子定理就像个神奇的魔法师，能把这团乱麻给理得清清楚楚。

它的过程其实并不复杂，但却充满了智慧。

就好比你要去一个陌生的地方，你得先找到路吧。

孙子定理就是给你指引方向的那个东西。

咱先来说说啥是孙子定理。

简单来讲，就是能解决那种同余式组的问题。

啥叫同余式组？哎呀，别着急，听我慢慢说。

比如说有几个数，它们除以某个数的余数都相同，这时候孙子定理就能派上用场啦。

它能帮你找到一个符合这些条件的数。

这就好像是在玩拼图游戏，每一块都有它的位置，而孙子定理就是帮你把这些拼图准确无误地拼在一起的那个关键步骤。

那它具体是咋操作的呢？这可得好好讲讲。

首先呢，你得找出那些关键的数字，就像在拼图里找到那些关键的板块一样。

然后，通过一些计算和推导，逐步找到那个最终的答案。

举个例子哈，比如说有三个数，分别除以 3、5、7 的余数都知道，那咱就能用孙子定理来求出一个符合所有条件的数。

这过程就像是走迷宫，得一步步地试探，找到正确的路。

你说这神奇不神奇？咱老祖宗的智慧那可真是不容小觑啊！这孙子定理在很多地方都有用呢，比如密码学、计算机科学等等。

它就像是一个隐藏的宝藏，等待着我们去发掘和利用。

你想想，如果没有孙子定理，那遇到这些同余式组的问题该咋办呀？所以说呀，这孙子定理可真是个好东西！咱可得好好学学，把它掌握好，说不定啥时候就能派上大用场呢！你说是不是？这就是孙子定理的过程，虽然看似简单，但其背后蕴含的智慧可是无穷无尽的呀！咱可不能小瞧了它，要好好研究，让它为我们服务呢！。

数论-孙⼦定理（中国剩余定理）及应⽤x≡b1 (mod m1)x≡b2 (mod m2)......x≡bk (mod mk)例：x≡2 (mod 3) ①x≡3 (mod 5) ②x≡2 (mod 7) ③由①，x=3*k+2 ④，代⼊②中得：3*k+2 ≡ 3 (mod 5)3*k≡1 (mod 5)k≡2 (mod 5)∴k=5*l+2,代⼊④中得，x=15*l+8 ⑥将⑥代⼊③中，得15*l+6≡0 (mod 7)5*l +2≡0 (mod 7)l ≡ 1 (mod 7)∴l = 7*n+1代⼊⑥中，得x=105*n+23∴x最⼩为23Th1:孙⼦定理（实在打不出来了>^<，放图）Th2:⼀次同余式组x≡b1 (mod m1) ①x≡b2 (mod m2) ②有解，当且仅当(m1,m2) | b2-b1,且有解时关于模[m1,m2]有唯⼀解证明：（必要性，有解->(m1,m2) | b2-b1）∵①、②有解，故存在x0,有x0≡b1 (mod m1)x0≡b2 (mod m2)设d=(m1,m2),则x0≡b1 (mod d)x0≡b2 (mod d)∴0≡b2-b1 (mod d)即b2≡b1 (mod d)∴d=(m1,m2) | b2-b1（充分性， (m1,m2) | b2-b1 -> 有解）由①，x=m1*y+b1故m1*y+b1≡b2 (mod m2)即m1*y+b1-b2 ≡0 (mod m2) ③∵ (m1,m2) | b2-b1 ∴同余式③有解（根据定理：a*x≡b (mod p) 若想此同余式有解，当且仅当(a,p)|b）∴（两边同时除上d）(m1/d)*y+((b1-b2)/d) ≡ 0 (mod m2/d)∵(m1/d,m2/d)=1,故存在y0(0≤y0≤m2/d)有y=(m2/d)*t+y0(t=0,±1,±2...)代⼊x=m1*y+b1中，得x=(m1*m2)*t/d+m1*y0+b1(t=0,±1,±2...)∴x≡C<m1*y0+b1> (mod [m1,m2])注：孙⼦定理中要求模m1,m2,...,mk两两互素，若不互素，则如下：x≡b1 (mod m1)x≡b2 (mod m2)((m1,m2)≠1)可算出x≡B (mod [m1,m2])再将此式与其他式⼦组合，再计算其解。