初等数论同余.ppt

《初等数论同余.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、在日常生活中，我们常接触到一些周期为正整数性的问题.例如：问火车下午2点从金华出发,30小时后到广州,则到广州是几点?就是24去除30所得的余数6加2,即晚上8点到广州,这就是同余问题.今天是星期一,问过了100天后是星期几等……．,现在同余理论已发展成为初等数论中内容丰富，应用广泛的一个分支．第三章同余§1同余的概念及其基本性质定义：给定一个正整数m，我们把它叫做模，如果用m去除任意两个整数a与b所得的余数相同，我们就说a,b对模m同余，记作如果余数不同，我们就说a,b对模m不同余，记作注1：上面所说的模m>1,因为m=1对所有整数就都同余了。注2:同余和整除有密切关系,可相互转化,有下面定

2、理.定理1：整数a,b对模同余的充分与必要条件是：m

3、a-b,即a=b+mt,t是整数。证明：设a=mq1+r1,b=mq2+r2,若则r1=r2,有a-b=m(q1-q2).即m

4、a-b反之若m

5、a-b,则m

6、m(q1-q2)+(r1-r2),因此m

7、r1-r2,但

8、r1-r2

9、

10、于等式中的两个等式相加和移项.结合前二条性质,我们来看几个例子.例1:对任意整数a,8a+7不可能是三个整数的平方.证:因为对任意的整数有所以对任意的有两边不同余.所以不相等.即对任意整数a,8a+7不可能是三个整数的平方.例2证明没有整数解.证:因为一个平方数除以4的余数能为0或者1所以左边除以4的余数只能是0,1,或3,而右边除以4的余数为2不同余,所以不定方程无解.性质3、若则有特别地，若则设若则有性质4若a=a1d,b=b1d,(d,m)=1,则证：由已知性质5(1)若k>0则(2)若d

11、(a,b,m),d>0,则证:性质5显然.性质6若则证：由已知m

12、a-b,又d

13、m,所以d

14、a-b

15、性质7d

16、(a,b),(d,m)=1则证：因为，(d,m)=1，所以有性质8若则(a,m)=(b,m)证：由已知a=b+mt,故(a,m)

17、a,(a,m)

18、m,有(a,m)

19、b,所以有(a,m)

20、(b,m),同理可证(b,m)

21、(a,m),即(a,m)=(b,m).性质9若则证：由已知,即a-b是所有的公倍数，而最小公倍数整除所有公倍数，即有例1：证明13

22、42n+1+3n+2证：∵42n+1+3n+2≡4·16n+9·3n≡3n(4+9)≡13×3n·≡0(13)∴13

23、42n+1+3n+2注：整除问题和同余问题是相互可以转化的把整除问题转化为同余问题是一种常用的方法.例2：证明5y+3=x

24、2无解证明：若5y+3=x2有解，则两边关于模5同余有5y+3≡x2(mod5)即3≡x2(mod5)而任一个平方数x2≡0,1,4(mod5)∴3≡0,1,4(mod5)，不可能∴即得矛盾，即5y+3=x2无解注：在证明方程无解时，经常用不同余就不相等的方法。§2同余的应用1、算术中的整除规律(1)个位数是偶数的数能被２整除；(2)个位数是０或５的数能被５整除；(3)末两位数能被４（或２５）整除的数能被４（或２５）整除；(4)末三位数能被８（或１２５）整除的数能被８（或１２５）整除；5)各位数字之和能被３（或９）整除的数能被３（或９）整除；6)奇数位数字之和与偶数位数字之和的差能被１１整除的

25、数能被１１整除。7)设b=7（11，13），则b

26、a的充分必要条件是b

27、注:整除规律一方面给出了整除的判定.另一方面也给出了求余数的方法.上述性质的证明差不多,我们证明其中的(6)(7)二条作一示范.规律(6)的证明证:设因为两边分别乘以然后相加有即奇数位数字之和与偶数位数字之和的差能被11整除的数能被11整除.规律(7)的证明证：一般地有两边同乘有并对n+1个式子相加得即有7

28、a的充要条件是7

29、对模11和13同理可证。注：这里用的是1000进制。例1:1234567891011…2005除以3的余数是多少.解:因为一个数除以3的余数,即其各位数字和除以3的余数.所以所求余数所以余数为1.例2

30、：设数62XY427是99的倍数，求X，Y解：因为99=9*11，所以有9

31、62XY427所以9

32、6+2+X+Y+4+2+7，即9

33、21+X+Y又有11

34、62XY427，有11

35、（7+4+X+6-2-Y-2）即11

36、（X-Y+13）因为0X，Y9，所以有2121+X+Y39，4X-Y+1322，由此可知21+X+Y=27，X-Y+13=11或21+X+Y=36，X-Y+13=22X+Y=6，X-Y