同余的基本概念和性质教学内容.ppt

《同余的基本概念和性质教学内容.ppt》由会员分享，可在线阅读，更多相关《同余的基本概念和性质教学内容.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、同余的基本概念和性质第三章第三章 同同 余余同余是数论中的一个基本概念。本同余是数论中的一个基本概念。本章除介绍同余的基础知识外，还要章除介绍同余的基础知识外，还要介绍它的一些应用。介绍它的一些应用。第一节第一节 同余的基本性质同余的基本性质定理定理3 设设a，b，c，d是整数，并且是整数，并且a b(mod m)，c d(mod m)，(1)则则 ()a c b d(mod m)；()ac bd(mod m)。证明证明 ()由式由式(1)及定义及定义1可知可知 m a b，m c d，第一节第一节 同余的基本性质同余的基本性质因此因此 m(a c)(b d)，此即结论此即结论()；()由由式

2、式(1)及及定定理理1可可知知，存存在在整整数数q1与与q2使使得得a=b q1m，c=d q2m，因此因此ac=bd (q1q2m q1d q2b)m，再利用定理再利用定理1，推出结论，推出结论()。证毕。证毕。第一节第一节 同余的基本性质同余的基本性质定定理理4 设设ai，bi（0 i n）以以及及x，y都都是是整整数数，并且并且x y(mod m)，ai bi(mod m)，0 i n，则则(2)证明证明 留作习题。留作习题。第一节第一节 同余的基本性质同余的基本性质定理定理5 下面的结论成立：下面的结论成立：()a b(mod m),d m,d0 a b(mod d);()a b(mo

3、d m),k 0,k N ak bk(mod mk)；()a b(mod mi)，1 i k a b(mod m1,m2,mk)；()a b(mod m)(a,m)=(b,m)；()ac bc(modm),(c,m)=1 a b(mod m).第一节第一节 同余的基本性质同余的基本性质证明证明 结论结论()()的证明，留作习题。的证明，留作习题。()由由ac bc(mod m)得得到到mc(a b)，再再由由(c,m)=1和和第第一一章章第第三三节定理节定理4得到得到ma b，即，即a b(mod m)。证毕。证毕。第一节第一节 同余的基本性质同余的基本性质例例1 设设N=是整数是整数N的十进

4、制表示，即的十进制表示，即N=an10n an 110n 1 a110 a0，则，则()3|N()9|N()11|N ()13|N 第一节第一节 同余的基本性质同余的基本性质证明证明 由由100 1，101 1，102 1，(mod 3)及式及式(2)可知可知 N=(mod 3)，由上式可得到结论由上式可得到结论()。结论结论()，()用同样方法证明。用同样方法证明。第一节第一节 同余的基本性质同余的基本性质为了证明结论为了证明结论()，只需利用式，只需利用式(2)及及100 1，101 3，102 4，103 1，(mod 13)和和第一节第一节 同余的基本性质同余的基本性质注注:一一般般地

5、地，在在考考虑虑使使 被被m除的余数时，首先是求出正整数除的余数时，首先是求出正整数k，使得，使得10k 1或或1(mod m)，再将再将 写成写成的形式，再利用式的形式，再利用式(2)。第一节第一节 同余的基本性质同余的基本性质例例2 求求 被被7整整除除的的条条件件，并并说说明明1123456789能否被能否被7整除。整除。解解 100 1,101 3,102 2,103 1(mod 7),因因此此即即第一节第一节 同余的基本性质同余的基本性质由于由于789 456 123 1=455，7 455，所以所以7 1123456789。第一节第一节 同余的基本性质同余的基本性质解解 依次计算同

6、余式依次计算同余式22 4，24 16，28 256，216 154，232 1(mod 641)。例例3 说说明明 是否被是否被641整除。整除。因此因此 0(mod 641)，即即641 。第一节第一节 同余的基本性质同余的基本性质注注:一一般般地地，计计算算ab(mod m)常常是是一一件件比比较较繁繁复复的的工工作作。但但是是，如如果果利利用用Euler定定理理或或Fermat定理（见第四节）就可以适当简化。定理（见第四节）就可以适当简化。第一节第一节 同余的基本性质同余的基本性质解解 (25733 46)26 (733 4)26=7(72)16 426 7(1)16 426=(7 4

7、)26 326=3(35)5 3(7)5=3 7(72)2 21 29(mod 50)，即所求的余数是即所求的余数是29。例例4 求求(25733 46)26被被50除的余数。除的余数。第一节第一节 同余的基本性质同余的基本性质解解 我们有我们有71 3，72 1，74 1(mod 10)，因此，若因此，若77 r(mod 4)，则则 例例5 求求 的个位数。的个位数。现在现在 77 (1)7 1 3(mod 4)，第一节第一节 同余的基本性质同余的基本性质所以由式所以由式(3)得到得到即即n的个位数是的个位数是3。注注:一一般般地地，若若求求对对模模m的的同同余余，可可分分以以下下步步骤骤进

8、行：进行：()求出整数求出整数k，使，使ak 1(mod m)；()求出正整数求出正整数r,r k,使得使得 bc r(mod k);()a r(mod m)。第一节第一节 同余的基本性质同余的基本性质证明证明 由由42n+1 3 n+2=4 42n 9 3 n=4 16n 9 3 n 4 3n 9 3 n=13 3 n 0(mod 13)例例6 证证明明:若若n是正整数是正整数,则则13 42n+1 3 n+2.得证。得证。第一节第一节 同余的基本性质同余的基本性质证明证明 设设a=2k 1，当，当n=1时，有时，有a2=(2k 1)2=4k(k 1)1 1(mod 23)，即式即式(4)成

9、立。成立。例例7 证证明：若明：若2 a，n是正整数，是正整数，则则 1(mod 2n+2)。(4)第一节第一节 同余的基本性质同余的基本性质设式设式(4)对于对于n=k成立，则有成立，则有 1(mod 2k+2)=1 q2k+2，其中其中q Z，所以，所以 =(1 q2k+2)2=1 q 2k+3 1(mod 2k+3)，其其中中q 是是某某个个整整数数。这这说说明明式式(4)当当n=k 1也也成立。成立。由归纳法知式由归纳法知式(4)对所有正整数对所有正整数n成立。成立。第一节第一节 同余的基本性质同余的基本性质证明证明 由由a2 1(mod p)p a2 1=(a 1)(a 1)，所以必

10、是所以必是p a 1或或p a 1，例例8 设设p是是素素数数，a是是整整数数，则则由由a2 1(mod p)可以推出可以推出 a 1或或a 1(mod p)。即即a 1(mod p)或或a 1(mod p)。第一节第一节 同余的基本性质同余的基本性质解解 因为因为792=8 9 11，故，故792 n 8 n，9 n及及11 n。我们有我们有 8 n 8 z=6，以以及及 9 n 9 1 3 x y 4 5 z=19 x y 9 x y 1，(5)例例9 设设n的的十十进进制制表表示示是是 ,若若792 n,求求x，y，z。第一节第一节 同余的基本性质同余的基本性质11 n 11 z 5 4

11、 y x 3 1=3 y x 11 3 y x。(6)由于由于0 x,y 9，所以由式，所以由式(5)与式与式(6)分别得出分别得出x y 1=9或或18，3 y x=0或或11。第一节第一节 同余的基本性质同余的基本性质这样得到四个方程组：这样得到四个方程组：其其中中a取取值值9或或18，b取取值值0或或11。在在0 x,y 9的的条件下解这四个方程组，得到条件下解这四个方程组，得到 x=8，y=0，z=6。习习 题题 一一1.证明定理证明定理1和定理和定理2。2.证明定理证明定理4。3.证明定理证明定理5中的结论中的结论()()。4.求求81234被被13除的余数。除的余数。5.设设f(x)是是整整系系数数多多项项式式，并并且且f(1),f(2),f(m)都不能被都不能被m整除整除,则则f(x)=0没有整数解没有整数解.6.已知已知99 ，求，求 与与。