一次同余方程组和孙子定理

厦门大学教案学年度第学期院（系）数学科学学院任课教师祝辉林课程名称初等数论授课章节：第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的数。

【中国剩余定理-⼊门】-C++中国剩余定理也称孙⼦定理，是中国古代求解⼀次同余式组（见同余）的⽅法。

是数论中⼀个重要定理。

这玩意在luogu 居然有模板题：先来看⼀个问题：在《孙⼦算经》中有这样⼀个问题：“今有物不知其数，三三数之剩⼆（除以3余2），五五数之剩三（除以5余3），七七数之剩⼆（除以7余2），问物⼏何？”熟悉吗⼩学数学学过吗这样的问题是基本的中国剩余定理的运⽤，解题过程有三步：1. 找出三个数：从3和5的公倍数中找出被7除余1的最⼩数15，从3和7的公倍数中找出被5除余1的最⼩数21，最后从5和7的公倍数中找出除3余1的最⼩数70。

2. ⽤15乘以2（2为最终结果除以7的余数），⽤21乘以3（3为最终结果除以5的余数），同理，⽤70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗2得到和233。

3. ⽤233除以3，5，7三个数的最⼩公倍数105，得到余数23，即233。

这个余数23就是符合条件的最⼩数。

不得不佩服古⼈的智慧然后看回题⽬（链接在开头）(n −a 1)|b 1(n −a 2)|b 2...(n −a k )|b k变形成同余⽅程组之后：(n −a 1≡0)(mod b 1)(n −a 2≡0)(mod b 2)...(n −a k ≡0)(mod b k )很明显的，如果a ≡b (mod m )，则a +c ≡b +c (mod m )成⽴。

这个不难理解，稍微理解⼀下就可以了。

然后把上⾯同余⽅程组变形⼀下：n ≡a 1(mod b 1)n ≡a 2(mod b 2)...n ≡a k (mod b k )然后到这⾥就是中国剩余定理的裸题了。

但是需要注意的是因为题⽬问题，我们需要对每⼀个a i 作这样的操作：a [i ]=(a [i ]mod b [i ]+b [i ])modb [i ];然后还需要注意的就是，这道题⽬因为数据良(bian)⼼(tai)，所以还需要⽤快速乘来防⽌爆long long 的情况。

中国剩余定理（孙子定理）定义中国古代求解一次同余式组（见同余）的方法。

是数论中一个重要定理。

又称中国剩余定理。

编辑本段内容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。

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

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

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

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

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

这时候孙子定理就派上用场啦！比如说，有一堆物品，除以 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。

初等数论中的几个重要定理基础知识定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模的剩余，即。

并定义中和互质的数的个数，称为欧拉（Euler）函数。

这是数论中的非常重要的一个函数，显然，而对于，就是1,2，…，中与互素的数的个数，比如说是素数，则有。

引理：；可用容斥定理来证（证明略）。

定理1：（欧拉（Euler）定理）设＝1，则。

分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而也是与互质的个数，且两两余数不一样，故（），而（）＝1，故。

证明：取模的一个既约剩余系，考虑，由于与互质，故仍与互质，且有，于是对每个都能找到唯一的一个，使得，这种对应关系是一一的，从而，。

，，故。

证毕。

这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。

定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。

设为质数，若是的倍数，则。

若不是的倍数，则由引理及欧拉定理得，，由此即得。

定理推论：设为质数，是与互质的任一整数，则。

定理3：（威尔逊（Wilson）定理）设为质数，则。

分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。

证明：对于，在中，必然有一个数除以余1，这是因为则好是的一个剩余系去0。

从而对，使得；若，，则，，故对于，有。

即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，，或，或。

除外，别的数可两两配对，积除以余1。

故。

定义：设为整系数多项式（），我们把含有的一组同余式（）称为同余方组程。

特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足：，则剩余类（其中）称为同余方程组的一个解，写作定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数，一次同余方程组，必有解，且解可以写为：这里，，以及满足，（即为对模的逆）。

中国剩余定理【定理概述】 中国剩余定理（孙⼦定理）是中国古代求解⼀次同余式组的⽅法。

是数论中⼀个重要定理。

⼀元线性同余⽅程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙⼦算经》卷下第⼆⼗六题，叫做“物不知数”问题，原⽂如下：有物不知其数，三三数之剩⼆，五五数之剩三，七七数之剩⼆。

问物⼏何？即，⼀个整数除以三余⼆，除以五余三，除以七余⼆，求这个整数。

《孙⼦算经》中⾸次提到了同余⽅程组问题，以及以上具体问题的解法，因此在中⽂数学⽂献中也会将中国剩余定理称为孙⼦定理。

【求逆元】逆元的含义：模p意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

ax≡1(mod p)。

⼀个数有逆元的充分必要条件是gcd(a,p)=1，此时逆元唯⼀存在，注意这⾥的唯⼀是指在群中唯⼀。

其实如果求出⼀个逆元x0，那么x0 + p*k都会满⾜上⾯的等式，但是我只取p内的正整数x0.【证明】由ax≡1(mod p)等价于这样⼀个⽅程a*x + p*y = 1 ，或者说这个⽅程x有解的话x必然满⾜ ax≡1(mod p)这个⽅程什么时候有解呢？很显然，当gcd(a,p) | 1时有解，所以gcd(a,p)只能是1，即a,p互质，证明完毕。

由此还可以得到⼀个结论，如果要求逆元，可以⽤扩展欧⼏⾥得求⼀组解（x,y），再求出x的最⼩正整数（x+p）%p,x就是a的唯⼀逆元。

⽅法1：费马⼩定理求逆元，p是，且gcd(a,p)=1在模为素数p的情况下，有费马⼩定理a p-1 ≡ 1（mod p）则a * a p-2 ≡ 1（mod p）所以a的逆元就是a p-2，⽤快速幂求即可。

#include<iostream>using namespace std;long long gcd(long long a, long long b){if(b == 0) return a;return gcd(b , a%b);}long long qPow(long long a ,long long n,long long mod){long long ans = 1;//如果n的⼆进制最后⼀位是1 结果参与运算//因为如果是0，那么幂运算之后该项是1,1乘任何数还是那个数，对结果不影响while(n > 0){if(n & 1)ans = (ans* a) % mod;a = (a*a) % mod;//底数加倍n >>= 1;//移位}return ans;}//long long invEle(long long a, long long mod){ //如果a 和模数不互质则必然不存在逆元if(gcd(a,mod) != 1 || mod < 2) return -1; return qPow(a,mod-2,mod);}int main(){long long a,b;int x,y;while(cin>>a>>b){cout<<invEle(a,b)<<endl;}}⽅法2：扩展欧⼏⾥得求逆元（⾼效）typedef long long ll;void extgcd(ll a,ll b,ll& d,ll& x,ll& y){if(!b){ d=a; x=1; y=0;}else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }}ll inverse(ll a,ll n){ll d,x,y;extgcd(a,n,d,x,y);return d==1?(x+n)%n:-1;}⽅法3：欧拉定理求逆元（很少⽤到）模p不是素数的时候需要⽤到欧拉定理逆元打表：typedef long long ll;const int N = 1e5 + 5;int inv[N];void inverse(int n, int p) {inv[1] = 1;for (int i=2; i<=n; ++i) {inv[i] = (ll) (p - p / i) * inv[p%i] % p;}}【解⽅程组】根据定理概述以及解法，得到以下⽅法int CRT(int a[],int m[],int n){int M = 1;int ans = 0;for(int i=1; i<=n; i++)M *= m[i];for(int i=1; i<=n; i++){int x, y;int Mi = M / m[i];extend_Euclid(Mi, m[i], x, y);ans = (ans + Mi * x * a[i]) % M;}if(ans < 0) ans += M;return ans;}【扩展中国剩余定理】当模数mi两两互质时有以上解法，当模数不确定是否两两互质呢？摘⾃博客:https:///acdreamers/article/details/8050018这种情况就采⽤两两合并的思想，假设要合并如下两个⽅程那么得到在利⽤扩展欧⼏⾥得算法解出的最⼩正整数解，再带⼊得到后合并为⼀个⽅程的结果为这样⼀直合并下去，最终可以求得同余⽅程组的解。

1 一次同余方程组同余是数论中的一个重要运算，在许多领域都有重要的应用t。

关于同余方程的解法已有一些基本的结论。

对于一次同余式的解的问题，已有下面的结果：ax≡b（modm），a≠0（modm）（1）定理1：同余式（1）有解的充分与必要条件是gcd（a，m）/b，且在有解的情况下，方程的解为：即方程的解数为gcd（a，m），其中x0是同余式（1）的一个特解。

本文基于同余的简单性质，主要讨论的是k阶一次同余方程的解法。

在我国古代的《孙子算经》里已经提出了这种形式的问题，并且得到了验证。

这就是著名的中国剩余定理。

a1x≡b1（modm1），a2x≡b2（modm2），…，akx≡bk（modmk）定理2：（中国剩余定理[1]）：设m1，m2，…，mk是k个两两互质的正整数，令m=m1m2…mk，且m=miMi，i=1，2，…，k，若a1=a2=…=ak=1，則同余式（1）的解是：X=M1'M1b1+M2'M2b2+…+Mk'Mkbk（modm）其中M1'M1=1（modmi），i=1，2，…，k。

显然，上述中国剩余定理中a1=a2=…=ak=1和m1，m2，…，mk是k个两两互质的正整数，这两个条件比较苛刻，很多情形下难以满足。

通过因子分解等手段可以将绝大部分的一次同余方程组化为满足中国剩余定理要求的形式[2]，一次同余方程组的阶数增大，导致计算的复杂程度增加。

本文主要讨论一般情形下的同余方程组解法。

2 中国剩余定理的不足之处中国剩余定理在数论中是个很重要的定理，应用于许多领域。

但是，若从解同余方程组的角度来看，也存在一些不足之处，并非首选。

文章就中国剩余定理的不足展开探讨，体现在如下3个方面。

2.1 标准化问题在前面已经提到，求解同余方程组（1），首先要求各个元素ai（mod mi）的逆元，化成满足中国剩余定理所要求的形式，即：x=a1-1b1（modm1），x=a2-1b2（modm2），…，x=ak-1bk（modmk）根据欧几里得算法或是辗转相除法得到：若gcd（ai，mi）=1，则ak-1存在。

一次同余式与一次同余式组的解的讨论摘 要: 这篇文章先给出有关同余式、同余式的解的概念，并在Euler 定理及孙子定理的基础上,详细地讨论了一次同余式、一次同余式组的是否有解的条件，若有解，则给出了求解方法. 一次同余式和一次同余式组的相关知识是学习数论过程中必须要掌握的知识，它在数学领域内有着及其广泛的应用。

关键词: 一次同余式; 一次同余式组;孙子定理;Euler 定理1引言南北朝时期的数学著作《孙子算经》中“物不知数”是这样的“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”解法和答案用算式表示为：702213152105223⨯+⨯+⨯-⨯=，即得到适合题意的最小正整数是23。

《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但真正从完整的计算程序和理论上解决这个问题的是南宋时期的数学家秦九韶。

秦九韶在他的《数书九章》不仅给出了一次同余式的解，而且用“大衍求一术”数学方法给出了一次同余式组的最小正整数解。

2基本定义和定理定义2.1 设1110()n n n n f x a x a x a x a --=++++ 是整系数多项式，m 是一正整数，称()0(mod )f x m ≡ (1)是模m 的同余式，若0(mod )n a m ≡/，则n 叫做同余式(1)的次数。

定义2.2 若a 是整数，且使得()0(mod )f a m ≡成立，则(mod )x a m ≡叫做同余式(1)的一个解。

即把适合(1)式且对模m 相互同余的一切数叫做同余式(1)的一个解。

定义2.3 欧拉函数()a ϕ是定义在正整数上的函数，它在正整数a 上的值等于序列0,1,2,,1a - 中与a 互质的数的个数。

定理2.1(Euler) 设1m >，(,)1a m =，则()1(mod )m a m ϕ≡。

证明 设12(),,,m r r r ϕ 是模数m 的一组简化剩余系，则由定理（若(,)1,a m x =通过m 的简化剩余系，则ax 通过模m 的简化剩余系.）可知12(),,,m ar ar ar ϕ 也是模m 的一组简化剩余系，故 12()12()()()()(mod )m m ar ar ar r r r m ϕϕ≡即 ()12()12()(mod )m m m a r r r r r r m ϕϕϕ≡ (﹡) 由于 ()i r ,1,1,2,,().m i m ϕ==故 12()(,)1.m r r r m ϕ= (﹡﹡)根据性质（若11,,(,)1,a a d b b d d m ===则11(mod ).a b m ≡） 以及 (﹡)和(﹡﹡)得 ()1(mod ).m a m ϕ≡定理2.2（孙子定理） 设12,,,k m m m 是k 个两两互素的正整数,12,(1,2,,),k i i m m m m m m M i k ===则同余式组1122(mod ),(mod ),,(mod )k k x b m x b m x b m ≡≡≡ (2)有唯一关于模m 的解111222(mod ),k k k x M M b M M b M M b m '''≡+++ (3) 其中1(mod )(1,2,,).i i i M M m i k '≡=证明 由于(,)1,i j m m i j =≠，即得(,)1i i M m =.由定理3.1知对每一i M ，有一i M '存在，使1(mod ).i i i M M m '≡由i i m m M =，知|,j i m M i j ≠. 故1(mod ),1,2,,.kjjji i i i i j M M bM M b b m i k =''≡≡=∑即(3)为(2)的解。

学院学术论文一次同余式组的解法A congruence of the solution姓名所在学院专业班级学号指导教师日期摘要:研究了有关同余式组的解法,特别是孙子定理的应用,当模不两两互质时,就不能用孙子定理来解了,那该怎么办呢?我们将在实例的求解中来揭密.[Summary] Has studied the related congruence group's solution, specially Residue theorem application, when the mold 22 are not coprime, could not use the Residue theorem to solve, how should that manage? We will reveal in the example solution.关键字:一次同余式组 模 孙子定理[Key words] A congruence group Mold Residue theorem 正文：引理 1. （孙子定理）设1m ，2m ………. km 是k 个两两互质的正数，m=12......k m m m , m=i i m M , i=1,2,…,k ,则同余式组x ≡1b (mod 1m ),x ≡2b (mod 2m )，…，x ≡k b (mod k m )的解为：x ≡`111M M b +`222M M b +…+`k k k M M b (modm ）,……(2)，其中`i M M ≡1（mod i m ）,i=1,2,…,k.证明：由（i m ，j m ）=1，i ≠j 即得（i M ，i m ）=1，故由§1定理即知对每一i M ，有一`i M 存在，使得`i i M M ≡1（mod i m ）.另一方面m=i m i M ,因此j m |i M ，i ≠j ，故`1k j j j j MM b =∑≡`i i i M M b ≡i b （mod i m ）即为（1）的解。

一次同余式与孙子定理知识扫描：1:本节将讨论一次同余方程和由此引申出的重要定理一一孙子定理，首先介绍若干概念。

设整系数多项式f x二a n x n• ||| •• a0,若有整数c,满足f c三0 modm ,则称c是满足同余方程的解，记作x三c mod m .(注：这是因为除以x 余c的数都满足这样方程)。

当且仅当c!,c2都是方程的解，且G与c模m不同余时，我们称d,c2是方程的两个不同解。

一般情况，我们说同余方程的解数，即指模仃两两不同余的解的个数。

2:最简单的同余方程是一次同余方程ax三b modm , m ?a同余方程有解的充要条件是a,m /b(注：必要性，若有解，则b可用a,x的式子表达，所以a,m /b;充分性，一^互素(a,m)(a,m)a m a m则可知p q 1= b p q b = b,因为a,m /b,则可知(a,m) (a,m) (a,m) (a,m)ax三b mod m有解)。

特别地，在(a,m)=1时，同余方程必有解。

事实上：(a,m)= 1, x遍历模m 的一组完系时，aX j也遍历模m的一组完系。

因此，有且仅有一个r0 =xi使得aX i三ar0三b modm，即同余方程至多有一个解。

进一步，一定存在a■使得a[_a三1(modm \于是x三a j(m^b(modm),即为(a,m )=1时，同余方程的解。

3.设k ■1,a i,b i是整数，m j是正整数，i=1,2, ||(,k,则称下面这k个同余式r=^mod m1)』a2x +b2三0(modm2)IIIa k x +b k三0(mod m k)为一次同余方程式组，显然，其中若有一个同余方程无解。

则方程组无解。

当其中每个同余方程都有解时，可将求解转化为求若干个下述方程的解。

x 三G(mod m1)』x 三q (mod m2)IIIx 三厲(mod m k)为了讨论上式的本质，我们先来看k=2的情况。

孙子定理的例题及求解孙子定理是数论中一个重要的定理，它可以用来求解关于同余方程的问题。

同余方程是指形如ax ≡ b (mod m)的方程，其中a、b、m为整数，x为未知数。

下面我们来看一个例题，并使用孙子定理来求解：例题：求解同余方程2x ≡ 3 (mod 5)。

解法如下：根据孙子定理，首先我们需要找到一个整数t，使得2t ≡1(mod 5)。

观察5的倍数，我们可以发现当t = 3时，2t = 6 ≡ 1 (mod 5)。

所以我们可以得出t = 3。

接下来，我们将同余方程中的系数和常数都乘以t，得到2xt ≡ 3t (mod 5)，即2xt ≡ 9 (mod 5)。

由于2xt ≡ 9 (mod 5)等价于2xt = 9 + 5k，其中k为整数。

我们可以将k表示为k = 2x'，其中x'为整数。

将k代入方程得到2xt = 9 + 5(2x')，化简得2xt = 9 +10x'。

由于t = 3，代入方程中得到6x = 9 + 10x'。

我们可以将此方程化简为6x - 10x' = 9，再因式分解得到3(2x - 5x') = 9。

进一步化简得到2x - 5x' = 3。

根据上式可知，当x' = 4时，方程成立。

此时，方程化简为2x - 5(4) = 3，解得2x = 23，即x = 12。

所以，同余方程2x ≡ 3 (mod 5)的解为x = 12。

通过上述例题的求解过程，我们可以看到孙子定理的应用。

它的核心思想是通过找到一个逆元素，将原同余方程转化为一个更简单的形式，然后通过化简和因式分解等方法，逐步求解得到最终的解。

孙子定理在密码学、编码和数论等领域有着广泛的应用。

第四章 同余式三、解答题1、设(,)1a m =，k 与m 是正整数，又设0(mod )k x a m ≡，证明同余方程(mod )kx a m ≡的一切解x 都可以表示成0(mod )x yx m ≡，其中y 满足同余方程1(mod )ky m ≡。

解：设1x 是0(mod )kx a m ≡的任意一个解，则一次同余方程01(mod )yx x m ≡有解y ，再由001()(mod )k k k k ky a y x yx x a m ≡≡≡≡得1(mod )ky m ≡，即1x 可以表示成0(mod )x yx m ≡，其中y 满足同余方程1(mod )ky m ≡； 反之，易知如此形式的x 是(mod )kx a m ≡的解。

2、解同余方程组()()31mod1047mod15x x ≡⎧⎪⎨≡⎪⎩解：这同余方程组的解与同余方程组()()()()31mod 2,31mod5,47mod3,47mod5x x x x ≡⎧⎪≡⎪⎨≡⎪⎪≡⎩的解相同，但第二个同余方程()31mod5x ≡可化为()2mod5x ≡, 第四个同余方程()47mod5x ≡可化为()2mod5x ≡-, 与()2mod5x ≡矛盾，所以原同余方程组无解.3、设素数2p >,求同余方程()21mod lx p ≡的解 解：同余方程可写为()()()110mod lx x p-+≡由于()1,1|2x x -+,所以上式等价于()10mod lx p -≡或()10mod lx p+≡因此，对任意的1l ≥解为()1,1mod l x p ≡- 解数为2.4、求同余式32()4560(mod 27)f x x x x =-+-≡ 解：∵()0(mod3),()0(mod3)f x f x '≡≡无公解∴20有唯一解0(mod3)x ≡以13x t =代入()0(mod9)f x ≡得1(0)3(0)0(mod9)f t f '+≡ 但(0)3(mod9)f ≡，(0)5(mod9)f '≡故1360(mod 9)t +≡，2120(mod 3)t +≡，11(mod 3)t ≡ 因此12213,39t t x t =+=+是()0(mod9)f x ≡的唯一解将239x t =+代入()0(mod 27)f x ≡得2(3)9(3)0(mod 27)f t f '+≡ 但(3)0(mod 27)f ≡，(3)8(mod 27)f '≡故2890(mod 27)t ⋅≡，280(mod 3)t ≡，20(mod3)t ≡设2333,327,3(mod 27)t t x t x ==+≡是()0(mod 27)f x ≡的唯一解。