数论 第三章 同余式02

2020/1/30数论1数论基础第三章同余式2020/1/30数论23.2中国剩余定理一中国剩余定理及其证明二中国剩余定理的应用三小结2020/1/30数论3一中国剩余定理及其证明定理1(中国剩余定理)设k1m,,m是k个两两互素的正整数，则对任意的整数k1b,,b，同余式组)1()mmod(bx)mmod(bxkk11一定有解，且解是唯一的.2020/1/30数论4一中国剩余定理及其证明(i)若令m=k,,1i,Mmm,mmiik1则同余式组(1)的解可表示为)mmod(bMMbMMxkk'k11'1其中k,1,2,im),1(modMMmmmmMi'ik1i1i1i(ii)若令1-k,,1i,mmNi1i则同余式组(1)的解可表示为x≡xk(modm1…mk).其中，是同余式组而i1ii'ix,1k,,2,1i),mmod(1NN2020/1/30数论5一中国剩余定理及其证明)mmod(bx)mmod(bxii11的解,i=1,…,k,并满足递归关系式)3()mmodm))(mmod)(xb(N(Nxxi1i1ii'1i1i1iii=2,…,k证明一首先，证明解的唯一性.设x,x’都是满足同余式(1)式的解，则X≡bi≡x’(modmi),i=1,…,k因为，k1m,,m是两两互素的正整数，根据2.1定理12，我们得到x≡x’(modm)定理12设m是一个正整数，则k,,2,1i),mmod(bai])m,,m[mod(bak12020/1/30数论6一中国剩余定理及其证明再证明解的存在性.(i)直接构造同余组的解：根据假设条件，对任意给定的i，1≤j≤k,j≠i又根据1.4定理3，有(mi,Mi)=1.再根据3.1定理2，或直接运用广义欧几里得除法，可分别求出整数Mi’,i=1,2,…,k,使得k,,2,1i)mmod(1MMii'i定理3设a1,…,an,c为整数，如果(ai,c)=1,1≤i≤n,则(a1…an,c)=1定理2设m是一个正整数，a是满足(a,m)=1的整数.则一次同余式ax≡1(modm)有唯一解x≡a’(modm)2020/1/30数论7一中国剩余定理及其证明这样，我们就构造出一个形为(2)式的整数，即)mmod(bMMbMMxkk'k11'1因为,ij,kj1,M|mMmmjiii及所以这个整数x满足同余式k,2,1i),mmod(bbMMxiiii'i也就是说，形为(2)式的整数是同余式(1)式的解.2020/1/30数论8一中国剩余定理及其证明证明二：归纳构造同余式组的解.k=1时，同余式)mmod(bxx)mmod(bx11111的解为k=2时，原同余式组等价于)4()mmod(bx)Nmod(bx2211由(4)式的第一个同余式有解),modN(bxx111我们2020/1/30数论9一中国剩余定理及其证明可以将同余式组的解表示为(y1待定参数)111yNxx将x代入同余式组(4)式的第二个同余式，我们有)5()mmod(xbyN)mmod(byNx2121122111或运用广义欧几里得除法，对整数N1及模m2，可求出整数'1N使得)mmod(1NN21'12020/1/30数论10一中国剩余定理及其证明将同余式组(4)的解为)mmmod))(mmod)(xb(N(Nxxx21212'1112假设i-1(i≥2)时，命题成立，即)mmod(bx)mmod(bx1i1i11有解)mmodm(xx1i11i2020/1/30数论11一中国剩余定理及其证明对于i，同余式组)mmod(bx)mmod(bxii11等价于同余式组)6()mmod(bx)Nmod(xxii1i1i2020/1/30数论12一中国剩余定理及其证明类似于k=2的情形，由同余式组(6)式的一个同余式有解1i1i1i1i1i1iyNxx)y(),modN(xx待定参数解表示为我们可以将同余式组的将x代入同余式组(6)式的第二个同余式，我们有)mmod(byNxii1i1i1i或)7()mmod(xbyNi1ii1i1i2020/1/30数论13一中国剩余定理及其证明运用欧几里得除法，对整数'1iN及模im，求出整数'1iN使得)mmod(1NNi1i'1i，将同余式(7)的两端同乘以'1iN，我们有)mmod)(xb(Nyi1ii'1i1i故同余式组(5)的解为)mmodm))(mmod)(xb(N(Nxxxi1i1ii'1i1i1ii根据数学归纳法原理，命题是成立的，证毕.2020/1/30数论14二中国剩余定理应用“物不知数”问题：今有物不知其数，三三数之有二，五五数之有三，七七数之有二，问物有多少？用同余式组表示就是7)(mod2x5)(mod3x)3mod(2x，实质上是解同余式组的正整数解.2020/1/30数论15二中国剩余定理应用这里1553M,2173M,3575M;7m,5m,3m321321容易算出可取1M,1M,2M'3'2'1，因此方程组的解为)105mod(23232211531212235x因此满足“物不知数”问题的正整数解是x=23+105t,t=0,1,…最小的值为232020/1/30数论16二中国剩余定理应用例1求解同余式组)11mod(bx)7mod(bx)6mod(bx)5mod(bx4321解令m=5·6·7·11=2310,1M=6·7·11=462,M2=5·7·11=385,M3=5·6·11=330,M4=5·6·7=2102020/1/30数论17二中国剩余定理应用分别求解同余式4,3,2,1i),mmod(1MMii'i得到1M,1M,1M,3M'4'3'2'1故同余式组的解为)2310mod(b210b330b385b4623x4321例2韩信点兵：有兵一对，若列成五行纵队，则末行一人；成六行纵队，则末行五人；成七行纵队，则末行四人；成十一行纵队，则末行十人，求兵数.2020/1/30数论18二中国剩余定理应用解：韩信点兵问题可转化为同余式组11)(mod10x7)(mod4x6)(mod5x)5mod(1x解一对10b,4b,5b,1b4321应用例1，得到x≡3·462+385·5+330·4+210·10≡6731≡2111(mod2310)2020/1/30数论19二中国剩余定理应用解二归纳构造同余式组的解令N1=5,同余式组的第一个同余式有解)5mod(1xx1我们将同余式组的解表示为(y待定参数)x=1+5y将x代入同余式组的第二个同余式，我们有1+5y≡5(mod6),或5y≡4(mod6)运用广义欧几里得除法，对整数N1=5及模m2=6,可求得整数)6mod(5NN11'1，我们有y≡5·4≡2(mod6)2020/1/30数论20二中国剩余定理应用故同余式组的解为30)(mod11251xx2我们将它表示为(y待定参数)30y11xx2将x代入同余式组的三个同余式，我们有11+30y≡4(mod7)或30y≡4-11≡0(mod7)运用广义欧几里得除法，对整数N2=30及模m3=72020/1/30数论21二中国剩余定理应用可求出整数),7mod(4NN12'2我们有y≡4·0(mod7)故同余式组的解为210)11(mod03011xx3我们将它表示为(y待定参数)210y11xx3将x代入同余式组的第四个同余式，我们有2020/1/30数论22二中国剩余定理应用11+210y≡10(mod11)或210y≡10-11≡10(mod11)运用广义欧几里得除法，对整数N3=210及模m4=11,可求出整数),11mod(1NN13'3我们有y≡1·10(mod11)故同余式组的解为210)2111(mod1021011xx32020/1/30数论23二中国剩余定理应用例32020/1/30数论24二中国剩余定理应用2020/1/30数论25二中国剩余定理应用2020/1/30数论26二中国剩余定理应用2020/1/30数论27二中国剩余定理应用的解相同，上述同余方程组满足定理1的条件，容易解出同余方程组的解为x≡-29(mod120)，(这里[8,20,15]=120),所以这也就是原同余式的解，且解数为一.2020/1/30数论28二中国剩余定理应用2020/1/30数论29二中国剩余定理应用2020/1/30数论30小结1.介绍中国剩余定理的基本内容及其证明.2.举例说明中国剩余定理的应用.3.掌握几种常见的同余式的解法2020/1/30数论31作业P80习题3.5315(1)