下载文档原格式
厦门大学教案学年度第学期院（系）数学科学学院任课教师祝辉林课程名称初等数论授课章节：第4.3节一次同余方程组和孙子定理授课教材：《初等数论》，北京大学出版社授课对象：数学类专业一年级本科生【教学要求】1. 了解孙子定理的历史背景和起源出处，理解用孙子定理求解一次同余方程组的思想方法和公式，掌握求解一次同余方程组的计算步骤；2. 掌握一次同余方程组的模两两不互素时，应当如何转化成模两两互素时的等价一次同余方程组，再用孙子定理求解；3. 理解一次同余方程组的意义，并能用孙子定理的方法解决一些实际应用问题。
【教学重点】1. 孙子定理的思想方法和计算步骤；2. 如何应用孙子定理解决实际应用问题。
【教学难点】理解孙子定理的思想方法。
【教学内容】第三节一次同余方程组和孙子定理本节主要讨论一次同余方程组的解法。
为了解决这类同余方程组，我们需要弄清楚剩余系的结构。
孙子定理(又称中国剩余定理)就是解决这类实际问题的有力工具。
一、“物不知其数”问题及其解法1.1问题的提出例1：（“物不知其数”问题）大约在公元四世纪，我国南北朝时期有一部著名的算术著作《孙子算经》，其中就有一个“物不知其数”问题：“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三”。
1.2 问题的解法及理由明朝程大位编著的《算法统宗》里记载了此题的解法，他是用一首歌谣叙述出来的：三人同行七十稀，五树梅花廿一枝。
七子团圆正月半，除百零五便得知。
这首诗翻译成数学算式就是：702213152233⨯+⨯+⨯=，233105223-⨯=。
解题步骤及理由如下：（1）先在5和7的公倍数中找除以3余1的数，进而找到除3余2的数。
因为[5,7]35=，35311÷=(余2)，(352)323⨯÷=(余1)，而(702)346⨯÷=(余2)，所以140符合条件。
（2）在3和7的公倍数中找除以5余1的数，进而找到除5余3的数。
中国余数定理公式中国余数定理，也称为孙子定理，是一种基于模运算的经典数学定理。
它能够将一个同余方程组转化为一个单同余方程，从而大大简化问题的求解。
这个定理在代数学、计算机科学、密码学等领域都有广泛的应用。
中国余数定理的原理假设给定两个正整数m1和m2，他们互质，对于任意两个整数a1、a2，下面的同余方程：x ≡ a1 (mod m1)x ≡ a2 (mod m2)都有一个解x在模m1m2下唯一确定。
特别的，当给定n个正整数m1、m2、...、mn，它们两两互质时，对于任意n个整数a1、a2、...、an，下面的同余方程组：x ≡ a1 (mod m1)x ≡ a2 (mod m2)...x ≡ an (mod mn)都有一个解x在模M=m1m2...mn下唯一确定。
中国余数定理的应用场景1. 线性同余方程组的求解中国余数定理可以将多个线性同余方程组转化为一个单一的同余方程，从而简化了求解问题。
在密码学领域中，线性同余方程组的求解常常涉及多个密码学密钥的计算和变换。
2. 数论问题的求解中国余数定理在数论领域中有广泛的应用。
它可以用来求解大量数据的最小公倍数，检测质数的性质，以及判断两个数是否是互质的。
3. 数据加密和解密中国余数定理可以用来设计和实现许多加密算法和协议，例如RSA加密算法和离散对数算法。
这些算法和协议通常需要利用中国余数定理来处理数字的加密和解密过程。
4. 编程语言中的应用在计算机科学领域，中国余数定理被广泛应用于编程语言中。
Java语言中可以利用中国余数定理来计算大型整数的模运算，而C++语言中则可以利用中国余数定理解决多项式求值问题。
总结：中国余数定理是一种重要的数学定理，常常在代数学、计算机科学、密码学等领域中得到广泛应用。
它能够将一个同余方程组转化为一个单同余方程，从而大大简化问题的求解。
在实际应用中，中国余数定理被广泛用于线性同余方程组的求解、数论问题的求解、数据加密和解密、以及编程语言中的应用等方面。
孙子定理解同余方程组（最新版）目录1.同余方程组的概念及孙子定理的背景2.孙子定理的概述3.同余方程组的求解方法4.中国剩余定理的证明5.孙子定理的应用及意义正文一、同余方程组的概念及孙子定理的背景同余方程组是数论中的一个重要概念，它是指一组包含多个同余方程的方程组。
例如，"物不知数"问题就是一道典型的同余方程组问题。
中国古代数学家孙子在《孙子算经》中提出了著名的"物不知数"问题，从而引出了同余方程组和孙子定理的研究。
二、孙子定理的概述孙子定理，又称中国剩余定理，是数论中的一个重要定理。
它是指对于一个同余方程组，如果其中某一个方程的解已知，则可以求出其他所有方程的解。
这个定理在我国古代数学中被誉为"孙子定理"，是中国古代数学的一项重要成果。
三、同余方程组的求解方法同余方程组的求解方法主要有两种，一种是基于孙子定理的解法，另一种是基于代数的解法。
基于孙子定理的解法是先求出其中一个方程的解，然后利用孙子定理求出其他方程的解。
而基于代数的解法则是利用代数的方法，通过一系列的运算和推导，求出同余方程组的解。
四、中国剩余定理的证明中国剩余定理的证明是基于数学归纳法的。
首先，对于一个简单的同余方程组，可以通过直接求解得到它的解。
然后，假设对于任意的 n-1 个同余方程，都可以通过孙子定理求出它的解，接下来需要证明当有 n 个同余方程时，也可以通过孙子定理求出它的解。
五、孙子定理的应用及意义孙子定理在数学中有着广泛的应用，它不仅被用于解决同余方程组问题，还被用于解决代数方程组、数论问题等领域。
关于孙⼦定理（中国剩余定理）及其证明孙⼦定理的内容：给出以下的⼀元线性同余⽅程组：(S ):x ≡a 1(mod m 1)x ≡a 2(mod m 2)…x ≡a n (mod m n )假设整数m 1,m 2,…,m n 两两互质，则对任意的整数：a 1,a 2,…a n ，⽅程组(S )有解，并且通解可以⽤如下⽅式构造得到：设M =m 1×m 2×…×m n =∏n i =1m i ，并设M i =Mm i ,∀i ∈1,2,…n 设t i =M −1i 为M i 模m i 的数论倒数（t i 为M i 模m i 意义下的逆元），即M i t i ≡1(mod m i ),∀i ∈1,2,…,n .⽅程组(S )的通解形式为x =a 1t 1M 1+a 2t 2M 2+…a n t n M n +kM =kM +∑n i =1a i t i M i ,k ∈Z .在模M 的意义下，⽅程组(S )只有⼀个解：x =∑n i =1a i t i M i (mod M )证明：从假设可知，对任何i ∈1,2,…,n ,j ≠i ,gcd (m i ,m j )=1，所以gcd (m i ,M i )=1.这说明存在整数t i 使得t i M i ≡1(mod m i ).这样的y i 叫做M i 模m i 的数论倒数。
考察乘积a i t i M i 可知：a i t i M i ≡a i ×1≡a i (mod m i )∀j ∈1,2,…,n ,j ≠i ,a i t i M i ≡0(mod m j )所以x =a 1t 1M 1+a 2t 2M 2+…+a n t n M n 满⾜：∀i ∈1,2,…,n ,x =a i t i M i +∑j ≠i a j t j M j ≡a i +∑j ≠i 0≡a i (mod m i )这说明x 就是⽅程组(S )的⼀个解。
中国剩余定理（孙子定理）定义中国古代求解一次同余式组（见同余）的方法。
是数论中一个重要定理。
又称中国剩余定理。
编辑本段内容1、分别找出能任两个数整除，而满足被第三个整除余几的数。
2、将三个未知数加起来，减去这三个数的最小公倍数的整数倍。
N≡R1(mod d1) ≡R2(mod d2)≡R3(mod d3)则N=k1d2d3R1+k2d1d3R2+k3d1d2R3±d1d2d3P其中P为任意非负整数k1是满足k1d2d3≡1(mod d1)的最小正整数k2是满足k2d1d3≡1(mod d2)的最小正整数k3是满足k3d1d2≡1(mod d3)的最小正整数编辑本段解法解法中的三个关键数70，21，15，有何妙用，有何性质呢?首先70是3除余1而5与7都除得尽的数，所以70a是3除余a,而5与7都除得尽的数，21是5除余1，而3与7都除得尽的数，所以21b是5除余b，而3与7除得尽的数。
同理，15c是7除余c，3与5除得尽的数，总加起来 70a+21b+15c 是3除余a，5除余b ，7除余c的数，也就是可能答案之一，但可能不是最小的，这数加减105(105=3*5*7)仍有这样性质，可以多次减去105而得到最小的正数解。
附：如70，其实是要找余2的，但只要找到了余1的再乘2即余二了。
孙子问题的解法，以现代的说法，是找出三个关键数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题中有三个数，分别为3、5、7，5*7/3余数为2，取35；3*7/5余数为1，要使余数为3，只需将3*7扩大3倍变成63即可；同样3*5/7的余数为1，要使余数为2，则将3*5扩大2倍，变成30。
§4同余式1 基本概念及一次同余式定义 设()110nn n n f x a x a xa --=+++ ，其中()0,0,1,,i n a i n >= 是整数，又设0m >，则()()0mod f x m ≡ （1）叫做模m 的同余式.若()0mod n a m ≡，则n 叫做同余式（1）的次数. 如果0x 满足()()00mod ,f x m ≡则()0mod x x m ≡叫做同余式（1）的解.不同余的解指互不同余的解.当m 及n 都比较小时，可以用验算法求解同余式.如 例1 同余式()543222230mod 7x x x x x +++-+≡仅有解()1,5,6mod 7.x ≡例2 同余式()410mod16x -≡有8个解()1,3,5,7,9,11,13,15mod16x ≡例3 同余式()230mod 5x +≡无解。
定理 一次同余式()()0mod ,0mod ax m a m ≡≡ （2）有解的充要条件是(),.a m b若（2）有解，则它的解数为(),d a m =. 以及当同余式（2）有解时，若0x 是满足（2）的一个整数，则它的(),d a m =个解是()0mod ,0,1,,1mx x k m k d d≡+=- （3） 证 易知同余式（2）有解的充要条件是不定方程ax my b =+ （4）有解. 而不定方程（4）有解的充要条件为()(),,.a m a m b =-当同余式（2）有解时，若0x 是满足（2）的一个整数，则()0mod ,0,1,, 1.m a x k b m k d d ⎛⎫+≡=- ⎪⎝⎭下证0,0,1,,1mx k k d d +=- 对模m 两两部同余. 设 ()00mod ,01,1m mx k x k m k d k d d d ''+≡+≤≤-≤≤-则()mod ,mod ,.m m m k k d k k d k k d d d ⎛⎫'''≡≡= ⎪⎝⎭再证满足（2）的任意一个整数1x 都会与某一个()001mx k k d d+≤≤-对模m 同余. 由()()01mod ,mod ax b m ax b m ≡≡得()101010mod ,mod ,.a a m m ax ax m x x x x d d d d ⎛⎫⎛⎫≡≡≡ ⎪ ⎪⎝⎭⎝⎭故存在整数t 使得10.mx x t d=+由带余除法，存在整数,q k 使得 ,0 1.t dq k k d =+≤≤-于是()()100mod .m mx x dq k x k m d d=++≡+故（2）有解时，它的解数为(),d a m =. 以及若0x 是满足（2）的一个整数，则它的(),a m 个解是()0mod ,0,1,,1mx x k m k d d≡+=- (5) 例1求同余式 ()912m o d 15x ≡ （6）的解. 解 因为()9,15 3.=又因312,故同余式（6）有解，且有三个解.先解()5mod 43≡x , 得().5mod 3≡x 故同余式（6）的三个解为()158mod15,0,1,2.3x k k ≡+= 即 ()3,8,13m o d 15.x ≡ 例2 求同余式 ()6483mod105x ≡ （7）的解. 解 ()831,1105,64= ,同余式有一个解. 将同余式表为21051921916152161054716476418864105836483+≡≡≡+≡≡≡+≡≡x ().105mod 622124≡≡例3 解同余式 325x ≡ 20 (mod 161) 解 ()1161,325= 同余式有一个解, 同余式即是3x ≡ 20 (mod 161) 即.161203y x +=解同余式 161y ≡ -20 (mod 3)， 即2y ≡ 1 (mod 3)， 得到y ≡ 2 (mod 3)，因此同余式的解是x ≡3161220⋅+= 114 (mod 161). 例4 设(a , m ) = 1，并且有整数δ > 0使得 a δ ≡ 1 (mod m )， 则同余式(2)的解是x ≡ ba δ - 1 (mod m ). 解 直接验证即可.注：由例4及Euler 定理可知，若(a , m ) = 1，则x ≡ ba ϕ(m ) - 1 (mod m ) 总是同余式(2)的解.注：本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用. 例5 解同余方程组⎩⎨⎧≡-≡+)7(mod 232)7(mod 153y x y x (8) 解 将(8)的前一式乘以2后一式乘以3再相减得到19y ≡ -4 (mod 7)，5y ≡ -4 (mod 7)， y ≡ 2 (mod 7).再代入(8)的前一式得到3x + 10 ≡ 1 (mod 7)，x ≡ 4 (mod 7)即同余方程组(8)的解是x ≡ 4，y ≡ 2 (mod 7).例6 设a 1，a 2是整数，m 1，m 2是正整数，证明：同余方程组⎩⎨⎧≡≡)(mod )(mod 2211m a x m a x (9) 有解的充要条件是a 1 ≡ a 2 (mod (m 1, m 2)). (10)若有解，则对模[m 1, m 2]是唯一的，即若x 1与x 2都是同余方程组(9)的解，则x 1 ≡ x 2 (mod [m 1, m 2]) (11)解 必要性是显然的.下面证明充分性.若式(10)成立，由定理2，同余方程m 2y ≡ a 1 - a 2 (mod m 1)有解y ≡ y 0 (mod m 1)，记x 0 = a 2 + m 2y 0，则x 0 ≡ a 2 (mod m 2)并且x 0 = a 2 + m 2y 0 ≡ a 2 + a 1 - a 2 ≡ a 1 (mod m 1)，因此x 0是同余方程组的解。
一次同余式与孙子定理 知识扫描：1：本节将讨论一次同余方程和由此引申出的重要定理——孙子定理，首先介绍若干概念。
设整系数多项式()10,n n f x a x a x a =+++若有整数c ，满足()()()1212120mod ,mod .(),,f c m c x c m x c c c c c m c c ≡≡则称是满足同余方程的解，记作注：这是因为除以余的数都满足这样方程。
当且仅当都是方程的解，且与模不同余时，我们称是方程的两个不同解。
一般情况，我们说同余方程的解数，即指模m 两两不同余的解的个数。
2：最简单的同余方程是一次同余方程()()()()()()()()()()()mod ,.,/(,/,,,1,,/,,,,mod )ax b m m a a m b a m a m b a m a m a m a mp q b p q b b a m b a m a m a m a m ax b m ≡+=⇒+=≡同余方程有解的充要条件是注：必要性，若有解，则b 可用a,x 的式子表达，所以；充分性，互素则可知因为，则可知有解。
Œ()()()()()()()001,1,1mod ,1mod ,mod ,,1i i i i m a m a m x m ax m x ax a b m a a a m x ab m a m -==='≡≡'≡≡=特别地，在时，同余方程必有解。
事实上：，遍历模的一组完系时，也遍历模的一组完系。
因此，有且仅有一个r 使得r 即同余方程至多有一个解。
进一步，一定存在使得于是即为时，同余方程的解。
j()()()()()()11122211223.1,,0mod 0mod 0mod mod mod mod i i i kk k k k k a b m a x b m a x b m a x b m x c m x c m x c m >+≡⎧⎪+≡⎪⎨⎪⎪+≡⎩≡⎧⎪≡⎪⎨⎪⎪≡⎩设是整数，是正整数，i=1,2,,k,则称下面这k 个同余式为一次同余方程式组，显然，其中若有一个同余方程无解。
则方程组无解。
当其中每个同余方程都有解时，可将求解转化为求若干个下述方程的解。
为了讨论上式的本质，我们先来看k=2的情况。
()()()()()()()()()()()()()()()()()1212121212112121121212121212111212121112121.mod ,m i j ij i j ij m m m x m x m x m x m x x m m x m x m m m m m m m x m x x m x m m x m x x m x ==+=+==+≡++≡+定理：设是模的完全剩余系，是模的完全剩余系，则x 是模的完全剩余系。
（即，分别遍历模，模的完全剩余系时，x 遍历模的完全剩余系。
）证明：此时x 共有个数，因而只需证明它们对两两不同余。
若则()()()()()()()()()()()()()11112122212111212212121121121od =mod =1=1m x x x m x x m x m x x m m m m m x m m x m +≡+=则，同时，则，定理得证！定理刻画了完系的某种结构，表明大模的完系，可以表示为两个较小的模的完系的“组合”。
同时我们应注意到，，，遍历模的完系时也遍历模的完系（这个性质非常常用并且有用）()()()()()()()()()()()()12121212122112121212121212122,,1,,3,,1,ij k k j j kkk k m m m m m x x m m x m x m x m m m m m m m m m m m M j k x M x M x M x x x x m m m x m m m m ===+==≤≤=+++=定理：设分别遍历模，的完全剩余系，则遍历模的完全剩余系。
进一步分析，我们可以得到一般情形的刻画。
定理：设两两既约，再设及那么当，，，分别遍历模，，，的完全剩余系时，遍历模()()()()()()()1111111111112..()2k n n n n n n n n n n n n n n n k mmx x m m m m m m m x m x m x m m m m k ++++++++++==++=+=的完全剩余系。
证明：时，即定理2设k=n 时定理成立。
当k=n+1时，记x 我们有x 注：与互素，x 遍历的完系，遍历模的完系由当时上式成立，命题得证！。
定理4：孙子定理（中国剩余定理）()()()()()()()121122111111222112,,,mod mod mod mod ,,1,1mod 1k k k k k k k j j j j j m m m x c m x c m x c m x M M c M M c M M c m m m m m m m M j k M M m j k ----≡⎧⎪≡⎪⎨⎪⎪≡⎩≡++==≤≤≡≤≤设是两两既约的正整数，那么同余方程：的解是这里孙子定理依旧刻画的是剩余系的结构，请读者将其与定理3进行对比，可以看出，孙子定理是着重刻画一组已定下的较小模的剩余类与一个较大的模的某个剩余类间的关系。
中国剩余定理在做题时的指导在于它能断定同余方程组的模两两互素时，一定有解。
甚至有些时候，我们并不关心解的是什么，而关注是否有解，怎样使其有解。
例题分析例1：解同余方程组()()()()()()()()1234123411mod 31mod 52mod 72mod113,5,7,11,57113711,5311,5731111mod 3,x x x x m m m m M M M M M ≡⎧⎪≡-⎪⎨≡⎪⎪≡-⎩========≡--≡解：取这时，又由()()()()()()()()()()111111121112222311133334141mod 3,=1.2211mod 5,1mod 5,=1.3544mod 7,14mod 7,=2.3576mod11,=2.394mod1155.M MMM M M M M M M M M M M M M x ----------≡≡≡-≡≡≡≡⨯⨯≡≡≡≡⨯⨯≡≡所以可取由所以可取由所以可取由所以可取由孙子定理知同余方程的解为：例2：任意给定的整数n ，证明：一定存在n 个连续正整数，其中每一个都有大于1的平方因子。
证明：由于素数有无穷多个，因而对于任意的n ，均可选出n 个不同的素数12,,,n p p p 。
考虑同余方程组()222212mod ,i n x i p p p p ≡-由于，，，显然两两互素，由中国剩余定理知上述同余方程组有解，于是1,2,,x x x n +++这n 个数分别被22212n p p p ，，，整除，命题得证！评注：在构造同余式时，选择质数的某些形式作为模式十分有效的，再看一个构造的例子。
()()()(){}123200512200511,,n S S k x x x 例：能否找到含有个自然数的集合，使中任意两数互素；中任意个数的和为合数。
分析与解：显然是“年份数据”，为此考虑n 个元素的集合，由于同时满足上述两个条件不易找到一个直接构造，只能一步步地探索。
对于满足的n 元集合石容易构造的，故设我们已找到一个满足的集合下面关心怎样更进一步约束或者变动该集合。
我们当然希望需要控制的“k 数和”变少自然想到了归纳构造。
我们{}{}()()1212111211,,,12n n n nn n n n n nx x x x x x x x x x x k x k C C +++-≥++设已经满足了上述两个条件，下面用推出应为何物。
中含的“k 数和”有2个注：含的数和个数为：()()()()1211122112121211111211121111221,,,,,+++mod ,,, 1.n n n n n n n n n n n n n n n n i i i i S S S T S x T S x T S x x S x x S x x S x x x S T p p p p +++---++++++-++-=-=-=----≡-≡-≠设这些和为则均为定值，我们想让，，，均为合数，这利用中国剩余定理是容易办到的，因为同余方程组：是有解的，其中p 是两两互素的数，且这样我们就让{}(){}()()1+11+11+111+1+11,,2,,1,,1,,1mod .n n i n n n n n n x x x x p x x x kx x x x x x x +≡满足回头看此时是否满足呢？这一点并不确定，从而应当控制一下的值。
由于已经是两两互质，所以若能表示为的形式，则两两互素，这实际上要求()()()1221121112121,2mod 1,2,,21,1mod ,2005n n i n n n n i i n n n p p p p a a a x T p i x a a a x n -+++-≡-=-≡=至此，怎样控制已经非常明确了，我们只需个质数，，，它们均与互素，考虑个同余式由中国剩余定理，这样的存在。
至此完成了归纳构造！特别的，时我们能找到一个适合题目要求的集合。
()()()()()()121121231240,1,21,,,,,,,121,031204132051243061624530n n n n a a a a a a a a a a a a n n n n n n n n -======例：求具有下述性质的，存在，，的排列使得恰好构成模的完全剩余系。
解：首先实验几个较小的，时，显然满足条件，时，满足条件时，，，满足条件，时，，，，满足条件，时，，，，，满足时，经实验没有满足条件的排列，n=7时，，，，，，，满足条件，n=8时，没有满足要求的排列。
通过上述实验，我们猜想n 为质数时，均是满足条件，尽管这可能是不全面的。
()()()()()()()()1121212,3,,,,0mod 1,mod ,11mod .1,10mod ,=0k kk k k k k k k p p p p p p k p b b b k b k p a c p k b a k k p a a a a a a a a p a p p p a a a =≡-≡=-≡-≡=-≡≡≠下面证明这个结论。
事实上，对任意质数，由中国剩余定理，对每个存在使得用表示被除的余数k=2,3,,p 则注：实际上是为了得到令下面证明，，，互不相同从而，，，是模的完系事实上，由有，故。
