初等数论(闵嗣鹤、严士健)第三版课件

《初等数论(闵嗣鹤、严士健)第三版课件》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。〔《孙子算经》〕§4.2孙子定理分析：设所求物数为x，则有xxx2(mod3),3(mod5),2(mod7).称之为同余式组。即要求这些同余式的公共解。一般地，xa(modmxa),(modm),,xa(modm)1122kk12问题：今有物不知其数，三三数之剩二，五五数之问题1：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。〔《孙子算经》〕剩二，七七数之剩二，问物几何。x-2是3、5、7的公

2、倍数。除余数最小公倍衍数乘各总答数最小数数率答数问题2：今有物不知其数，三三数之剩二，五五数之323×5×75×7235×2×3140+63+233-=105302×105=剩三，问物几何。=23323xk3253k533×7121×1×33

3、xx2,5

4、312723×5115×1×2记且xn52,51n(mod3),则；522n(mod3)1111记且xn33,31n(mod5),则333n(mod5).2222另外，显然有5,

5、x3,

6、x12从而有xx2(mo

7、d3),xx3(mod5).312124为什么啊？1一、同余式组的解法——中国剩余定理问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。〔《孙子算经》〕定理1[孙子定理]设有同余式组xb(modmxb),(modm),,xb(modm)(1)1122kk记且xn572,57n1(mod3),则；x2(mod3)1111m,m,,m是两两互质的正整数，12k记且xn373,37n1(mod5),则x3(mod5).2222m记m=m1m2mk，

8、Mii,1k.记且xn352,35n1(mod7),则x2(mod7).mi3223k另外，显然有57,37,35,

9、x

10、x

11、x则(1)的解为xbiiiMMm(mod)(2)123i1令xxxx,123其中，整数M（1ik），满足MM1(modm).iiii则有xxx2(mod3),3(mod5),2(mod7).56证明：由(M,m)=1，利用辗转相除法可以求出ii反之，若x1是（1）的解，M与y，使得MMym=1，iiiiii则xb(mo

12、dm).1iiMM'1(mod)miii又m,m,,m两两互质，12kbMMb(modm)，1ik。iiiii所以xb(modm).由mMmMmmm,(,)1mMi,.j1iiijjijijkbMMbMMb(modm)故方程（1）的解只能为（2）式。jjjiiiiij1k注(1)历史上,宋代数学家秦九韶曾称该方法为“求一术”,bMMjjjib(mod[mm12,,,mk])bi(modm)该定理常称为中国剩余定理.j1k(2)很显然,利用孙子定理解

13、题的关键是求出M.ixbjjjMMm(mod)满足方程(1).j1782eg1解同余式组xxx2(mod3),3(mod5),2(mod7).例2〔韩信点兵〕有兵一队，若列成五行纵队，则末行1人；成六行纵队，则末行5人；成七行纵队，解：mmm3,5,7两两互质，m=357105.123则末行4人；成十一行纵队，则末行10人。求兵数。MMM35,21,15.衍数123'解：即求解同余式组由MM1(modm)M'1,M'1,M'1乘率iii123xxxx1(

14、mod5),5(mod6),4(mod7),10(mod11).351(mod3)35(1)1(mod3);('M不唯一)i其中，mmmm5,6,7,11.1234211(mod5)2111(mod5);bbbb12341,5,4,10.——余数151(mod7)1511(mod7).kMM126711462,5711385,xbiiiMM()衍数乘率余数——衍数i1MM5611330,567210.34

15、235(1)3211215123(mod105)910列表如下：定理2在定理1的条件下，若式(1)中的b,b,,b12k分别通过模m,m,,m的完全剩余系，则式(2)中12k的x通过模mmm的完全剩余系。mbmM'bMMbMM'12kiiiMiiii'iiik5146231×462×3证明：由，xbiiiMMm(mod)6731i165231038515×385×1则x通过mmm个整数，211112k