当前位置：文档之家 › 同余定义和性质

同余定义和性质

  • 格式：ppt
  • 大小：95.00 KB
  • 文档页数：14

下载文档原格式

  / 14

合集下载

同余的基本概念和性质

同余的基本概念和性质

模相等的同余关系的运算性质
模相等的同余关系满足交换律和结合律 模相等的同余关系满足消去律 模相等的同余关系满足分配律 模相等的同余关系满足幂等律
同余的应用
同余在模方程中的应用
模方程的同余解法 同余在模方程中的应用实例 同余在模方程中的求解步骤 同余在模方程中的优势与局限性
同余在数论中的应用
整除理论：同余是整除理论中的重要概念，用于研究整数之间的除法关系。
● - 同余关系具有反身性，即任意整数a都与自身对模m同余，即a≡a(mod m)。 ● - 同余关系具有对称性，即如果a≡b(mod m)，则b≡a(mod m)。 ● - 同余关系具有传递性，即如果a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)。 ● - 对于任意整数a、b和c，若a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)。
同余的性质
模相等的同余关系
● 定义：如果两个整数a和b除以同一个正整数m的余数相同，则称a和b对模m同余，记作 a≡b(mod m)。
● 性质： - 同余关系具有反身性，即任意整数a都与自身对模m同余，即a≡a(mod m)。 - 同余关 系具有对称性，即如果a≡b(mod m)，则b≡a(mod m)。 - 同余关系具有传递性，即如果 a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)。 - 对于任意整数a、b和c，若a≡b(mod m)且 b≡c(mod m)，则a≡c(mod m)。
同余的基本概念和性质
汇报人：XX
目录
同余的定义
同余的性质
01
02
同余的应用
同余的证明方法
03
04
同余的定义
什么是同余
同余的定义：两个整数除以某 个固定整数得到的余数相同， 则称这两个整数同余。

同余

同余

可以理解为： 31除以4的余数是3 可以理解为： 50除以4的余数是18
求123+72的和除以10的余数
方法一：123+72=195
求121+74的和除以3的余数
方法一：121+74=195
求121-74的差除以3的余数
方法一：121-74=47
同余式定义和基本性质
若ab(mod m), cd(mod m), k为正整数 ①可加减性 和（差）的余数等于余数的和（差） 即a±c b±d(mod m), 特别地有a±k b±k(mod m). 同时有a-b 0（mod m） 显然：移项变号同样适用于同余式
【例7】若今天是星期六，从今天 102003天后的那一天是星期（ ）
10 3(mod7)
6
10
2003
3
2003
(mod7)
3 （ 1 mod7） 2003 6 333 5
10
2003
3 3
2003
5
5(mod7)
∴所求那天是星期四。
一次同余式组
• 本节介绍一次同余式组的解法及其应用举 例． • 在公元三世纪前,《孙子算经》里已提出了下 面的同余式组 xb1(mod m1), xb2(mod m2),…, xbk(mod mk) (1) • 这种形式的问题, 并且很好地解决了它.《孙子 算经》里所提出的问题之一如下: • “今有物不知其数, 三三数之剩二, 五五数之 剩三, 七七数之剩二. 问物几何？” “答日二 15:51:43 十三.”
一个数除以3余2，除以5余3，除以7余 2，求这个数。 被7除余2的数有：2，9，16，23
被5除余3的数有：3，8，13，18，23 被3除余2的数有：2，5，8，11，14，17 ，20，23

小升初数学复习知识点：余数、同余与周期

小升初数学复习知识点：余数、同余与周期

小升初数学复习知识点：余数、同余与周期余数、同余与周期一、同余的定义：①若两个整数a、b除以m的余数相同，则称a、b对于模m 同余。

②已知三个整数a、b、m，如果m|a-b，就称a、b对于模m 同余，记作a≡b（mod m），读作a同余于b模m。

二、同余的性质：①自身性：a≡a（mod m）；②对称性：若a≡b（mod m），则b≡a（mod m）；③传递性：若a≡b（mod m），b≡c（mod m），则a≡ c（mod m）；④和差性：若a≡b（mod m），c≡d（mod m），则a+c≡b+d （mod m），a-c≡b-d（mod m）；⑤相乘性：若a≡ b（mod m），c≡d（mod m），则a×c≡ b×d （mod m）；⑥乘方性：若a≡b（mod m），则an≡bn（mod m）；⑦同倍性：若a≡ b（mod m），整数c，则a×c≡ b×c（mod m×c）；三、关于乘方的预备知识：①若A=a×b，则MA=Ma×b=（Ma）b②若B=c+d则MB=Mc+d=Mc×Md四、被3、9、11除后的余数特征：①一个自然数M，n表示M的各个数位上数字的和，则M≡n （mod 9）或（mod 3）；②一个自然数M，X表示M的各个奇数位上数字的和，Y表示M的各个偶数数位上数字的和，则M≡Y-X或M≡11-（X-Y）（mod 11）；五、费尔马小定理：如果p是质数（素数），a是自然数，且a不能被p整除，则ap-1≡1（mod p）。

以上是数学网为小升初的考生们整理的小升初数学总复习知识点，希望能够关注到同学们。

更多内容请关注数学网小升初频道。

1.同余的概念及基本性质

1.同余的概念及基本性质

第三章 同余§1 同余的概念及其基本性质定义 给定一个正整数m ，若用m 去除两个整数a 和b 所得的余数相同，则称,a b 对模m 同余，记作()mod .a b m ≡若余数不同，则称,a b 对模m 不同余，记作()\mod a b m ≡.甲 ()mod .a a m ≡（甲：jia 3声调； 乙：yi 3声调； 丙：bing 3声调； 丁：ding 1声调； 戊：wu 声调； 己：ji 3声调； 庚：geng 1声调； 辛: xin 1声调 天； 壬: ren 2声调； 癸: gui 3声调.）乙 若()mod ,a b m ≡则()mod .b a m ≡丙 若()()mod ,mod ,a b m b c m ≡≡则()mod .a c m ≡ 定理1 ()mod |.a b m m a b ≡⇔-证 设()mod a b m ≡，则12,,0.a mq r b mq r r m =+=+≤<于是，()12,|.a b m q q m a b -=--反之，设|.m a b -由带余除法，111222,0,,0a mq r r m b mq r r m =+≤<=+≤<，于是，()()1221.r r m q q a b -=-+-故，12|m r r -，又因12r r m -<，故()12,mod .r r a b m =≡丁 若()()1122mod ,mod ,a b m a b m ≡≡则，()1212mod .a a b b m ±≡±证 只证“+”的情形.因()()1122mod ,mod a b m a b m ≡≡，故1122,m a b m a b --，于是()()()()11221212|m a b a b a a b b -+-=+-+，所以()1212mod .a a b b m +≡+ 推论 若()mod ,a b c m +≡则()mod .a c b m ≡-戊 若()()1122mod ,mod ,a b m a b m ≡≡则()1212mod .a a bb m ≡ 证 因()()1122mod ,mod a b m a b m ≡≡，故1122|,|.m a b m a b --又因()()()1212111212211122,a a bb a b b a bb a a b b a b -=-+-=-+-故()12121212|,mod .m a a bb a a bb m -≡ 定理2 若()()11mod ,mod ,1,2,,,kki i A B m x y m i k αααα≡≡=则()11111111,,,,mod .k k k kkkk k A xx B y y m αααααααααααα≡∑∑特别地，若()mod ,0,1,,i i a b m i n ≡=，则()111010mod .n n n n n n n n a x a x a b x b x b m ----+++≡+++证 因()mod ,1,2,,i i x y m i k ≡=故,1,2,,iii i x y i k αα≡=，从而()1111mod .k k k k x x y y m αααα≡又因()11mod kkA B m αααα≡，故()()111111111111111,,,,mod ,mod .k k kk k k kkkk k k k A xx B y y m A xx B y y m αααααααααααααααααααα≡≡∑∑己 若()()mod ,,1,ka kb m k m ≡=则()mod .a b m ≡证 因()mod ka kb m =，故()|.m ka kb k a b -=-又因(),1k m =，故()|,mod .m a b a b m -≡庚 （ⅰ）若()mod ,0,a b m k ≡>则()mod .ka kb km ≡ （ⅱ）若()mod ,|,|,|,0,a b m d a d b d m d ≡>则mod .a b m d d d ⎛⎫≡ ⎪⎝⎭证 （ⅰ）因()mod ,0a b m k ≡>，故()()|,|,mod .m a b km k a b ka kb ka kb km --=-≡（ⅱ）因()mod ,a b m ≡故|,.m a b a b mq --=又因|,|,|,0d a d b d m d >111111,,,0,0,0a da b db m dm a b m ===>>>. 于是()111111111,,mod ,mod .a b m da db dm q a b m q a b m d d d ⎛⎫-=-=≡≡ ⎪⎝⎭辛 若()mod ,1,2,,i a b m i k ≡=，则[]()12mod ,,,.k a b m m m ≡证 因()mod ,1,2,,i a b m i k ≡=，故|,1,2,,.i m a b i k -=于是，[][]()1212,,,|,mod ,,,.k k m m m a b a b m m m -≡附记 最小公倍数的一个常用性质是，若12|,|,,|k m a m a m a ，则[]12,,,|.k m m m a证 由带余除法，设[][]1212,,,,0,,,k k a m m m q r r m m m =+≤<，则12|,|,,|k m a m a m a 及12|,|,,|k m a m a m a 得， |,1,2,,.i m r i k =但[]12,,,k m m m 是12,,,k m m m 的最小公倍数，故[]120,,,,|.k r m m m a =壬 若()mod ,|,0,a b m d m d ≡>则()mod .a b d ≡证 因()mod ,a b m ≡故|.m a b -又因|,0d m d >，故()|,mod .d a b a m d -≡ 癸 若()mod a b m ≡，则()(),,.a m b m =证 因()mod a b m ≡，故|.m a b -于是，存在整数t 使得.a b mt -=故.a mt b =+故()(),,.a m b m =例 一个整数0a >被9整除的充分必要条件是n 的各位数字（十进制）的和倍9整除.证 设1101010,010n n n n i a a a a a --=+++≤<.因()101mod9≡，故()()101mod9,10mod9,0,1,,.i i i i a a i n ≡≡=于是，()010mod 9.n nii i i i a a a ===≡∑∑故9|a 的充分必要条件是09|.ni i a =∑作业 P53:2,3,4,5.习题选解2.设正整数1101010,010,n n n n i a a a a a --=+++≤<证明11整除a 的充分必要条件是11整除()01.niii a =-∑证 因为()101mod11≡-，故()()()()101mod11,101mod11,0,1,,.i ii i i i a a i n ≡-≡-=.于是，()()0101mod11.n nii iii i a a a ===≡-∑∑由此可得，11|a 的充分必要条件是()0111.nii i a =-∑3.找出能被37,101整除的判别条件来.解 （ⅰ）因()10001mod37≡，故()()10001mod370.ii ≡≥设11010001000,01000.n n n n i a a a a a --=+++≤<则由()10001mod37i≡得()1000mod37,0,1,,ii i a a i n ≡=，故()01000mod 37.n nii i i i a a a ===≡∑∑由此可得，37|a 的充分必要条件是037.ni i a =∑（ⅱ）因()1001mod101≡-，故()()()1001mod1010.iii ≡-≥ 设110100100,0100,n n n n i a a a a a --=+++≤<则由()()1001mod101ii ≡-得()()1001mod101,0,1,,ii i i a a i n ≡-=，故()01001.n niii i i i a a a ===≡-∑∑由此可得，101|a 的充分必要条件是()01011.niii a =-∑4.证明52641|2 1.+ 证 因()()8163222256,265536154mod 641,2154237166401mod 641,==≡≡=≡≡-故52641|2 1.+5.若a 是任一奇数，则()()221mod 21.nn a n +≡≥证 对n 作数学归纳法.当1n =时，因a 为奇数，故可设121a a =+，则()()2221111112114441a a a a a a -=+-=+=+.而()111a a +是两个连续两个整数的积，一定是2的倍数，从而()122128|1,1mod 2,a a +-≡即1n =时结论正确.假设对()12n n -≥结论正确，即()12121mod 2.n n -+≡下面说明在此假设下，对n 结论正确.因()()()111222221111nn n n a aa a ----=-=-+，而由归纳假设得121n a--是12n +的倍数，又因a 为奇数，故121n a -+也为奇数，于是()()112211n n a a ---+是22n +的倍数，故()221mod 2.nn a +≡。

小学奥数专题-同余问题

小学奥数专题-同余问题

1. 学习同余的性质2. 利用整除性质判别余数同余定理 1、定义:若两个整数a 、b 被自然数m 除有相同的余数，那么称a 、b 对于模m 同余，用式子表示为:a ≡b ( mod m )，左边的式子叫做同余式。

同余式读作:a 同余于b ，模m 。

2、重要性质及推论:（1）若两个数a ，b 除以同一个数m 得到的余数相同，则a ，b 的差一定能被m 整除例如:17与11除以3的余数都是2，所以1711 （）能被3整除．（2）用式子表示为:如果有a ≡b ( mod m )，那么一定有a －b ＝mk ，k 是整数，即m |(a －b )3、余数判别法当一个数不能被另一个数整除时，虽然可以用长除法去求得余数，但当被除位数较多时，计算是很麻烦的．建立余数判别法的基本思想是:为了求出“N 被m 除的余数”，我们希望找到一个较简单的数R ，使得:N 与R 对于除数m 同余．由于R 是一个较简单的数，所以可以通过计算R 被m 除的余数来求得N 被m 除的余数． ⑴ 整数N 被2或5除的余数等于N 的个位数被2或5除的余数；⑵ 整数N 被4或25除的余数等于N 的末两位数被4或25除的余数；⑶ 整数N 被8或125除的余数等于N 的末三位数被8或125除的余数；⑷ 整数N 被3或9除的余数等于其各位数字之和被3或9除的余数；⑸ 整数N 被11除的余数等于N 的奇数位数之和与偶数位数之和的差被11除的余数；（不够减的话先适当 加11的倍数再减）；⑹ 整数N 被7，11或13除的余数等于先将整数N 从个位起从右往左每三位分一节，奇数节的数之和与偶数节的数之和的差被7，11或13除的余数就是原数被7，11或13除的余数．模块一、两个数的同余问题【例 1】 有一个整数，除39，51，147所得的余数都是3，求这个数.例题精讲知识点拨教学目标5-5-3.同余问题【例 2】某个两位数加上3后被3除余1，加上4后被4除余1，加上5后被5除余1，这个两位数是______. 【例 3】有一个自然数，除345和543所得的余数相同，且商相差33．求这个数是多少？【例 4】一个大于10的自然数去除90、164后所得的两个余数的和等于这个自然数去除220后所得的余数，则这个自然数是多少？【例 5】两位自然数ab与ba除以7都余1，并且a b⨯．>，求ab ba【例 6】现有糖果254粒，饼干210块和桔子186个.某幼儿园大班人数超过40.每人分得一样多的糖果，一样多的饼干，也分得一样多的桔子。

小学奥数之 同余问题(含详细解析)

小学奥数之 同余问题(含详细解析)

1. 学习同余的性质2. 利用整除性质判别余数同余定理 1、定义：若两个整数a 、b 被自然数m 除有相同的余数，那么称a 、b 对于模m 同余，用式子表示为：a ≡b ( mod m )，左边的式子叫做同余式。

同余式读作：a 同余于b ，模m 。

2、重要性质及推论：（1）若两个数a ，b 除以同一个数m 得到的余数相同，则a ，b 的差一定能被m 整除例如：17与11除以3的余数都是2，所以1711 （）能被3整除． （2）用式子表示为：如果有a ≡b ( mod m )，那么一定有a －b ＝mk ,k 是整数，即m |(a －b )3、余数判别法当一个数不能被另一个数整除时，虽然可以用长除法去求得余数，但当被除位数较多时，计算是很麻烦的．建立余数判别法的基本思想是：为了求出“N 被m 除的余数”，我们希望找到一个较简单的数R ，使得：N 与R 对于除数m 同余．由于R 是一个较简单的数，所以可以通过计算R 被m 除的余数来求得N 被m 除的余数．⑴ 整数N 被2或5除的余数等于N 的个位数被2或5除的余数；⑵ 整数N 被4或25除的余数等于N 的末两位数被4或25除的余数；⑶ 整数N 被8或125除的余数等于N 的末三位数被8或125除的余数；⑷ 整数N 被3或9除的余数等于其各位数字之和被3或9除的余数；知识点拨教学目标5-5-3.同余问题⑸整数N被11除的余数等于N的奇数位数之和与偶数位数之和的差被11除的余数；（不够减的话先适当加11的倍数再减）；⑹整数N被7，11或13除的余数等于先将整数N从个位起从右往左每三位分一节，奇数节的数之和与偶数节的数之和的差被7，11或13除的余数就是原数被7，11或13除的余数．例题精讲模块一、两个数的同余问题【例 1】有一个整数，除39,51,147所得的余数都是3，求这个数.【考点】两个数的同余问题【难度】1星【题型】解答【解析】(法1) 39336-=，51-3=48，1473144-=，(36,144)12=，12的约数是1,2,3,4,6,12，因为余数为3要小于除数，这个数是4,6,12；(法2)由于所得的余数相同，得到这个数一定能整除这三个数中的任意两数的差，也就是说它是任意两数差的公约数．513912-=，(12,108)12-=，14739108=，所以这个数是4,6,12．【答案】4,6,12【例 2】某个两位数加上3后被3除余1，加上4后被4除余1，加上5后被5除余1，这个两位数是______. 【考点】两个数的同余问题【难度】2星【题型】填空【关键词】人大附中，分班考试【解析】“加上3后被3除余1”其实原数还是余1，同理这个两位数除以4、5都余1，这样，这个数就是[3、4、5]+1=60+1=61。

同余的概念与性质

同余的概念与性质同余：设m 是大于1的正整数，若用m 去除整数b a ,，所得余数相同，则称a 与b 关于模m 同余，记作)(mod m b a ≡，读作a 同余b 模m ；否则称a 与b 关于模m 不同余记作)(mod m b a ≠。

性质1：)(mod m b a ≡的充要条件是Z t mt b a ∈+=,，也即)(|b a m -。

性质2：同余关系满足下列规律：（1）自反律：对任何模m 都有)(mod m a a ≡；（2）对称律：若)(mod m b a ≡，则)(mod m a b ≡；（3）传递律：若)(mod m b a ≡，)(mod m c b ≡，则若)(mod m c a ≡。

性质 3:若,,,2,1),(mod s i m b a i i =≡则).(mod ),(mod 21212121m b b b a a a m b b b a a a s s s s ≡+++≡++推论： 设k 是整数，n 是正整数，（1）若)(mod m c b a ≡+，则)(mod m b c a -≡。

（2）若)(mod m b a ≡，则)(mod m a mk a ≡+；)(mod m bk ak ≡；)(mod m b a n n ≡。

性质4：设)(x f 是系数全为整数的多项式，若)(mod m b a ≡，则 ))(mod ()(m b f a f ≡。

性质5：若)(mod m bd ad ≡，且1),(=m d ，则)(mod m b a ≡。

性质6：若)(mod m b a ≡，且m d b d a d |,|,|，则)(mod d m d b d a ≡。

性质7：若)(mod m b a ≡，且m m |1，则)(mod 1m b a ≡。

性质8：若)(mod i m b a ≡，s i ,,2,1 =，则]),,,(mod[21s m m m b a ≡这里],,,[21s m m m 表示s m m m ,,,21 的最小公倍数。

同余的基本概念和性质

4 16，28 256，216 154，232 1 (mod 641)。
例3 说明 是否被641整除。
因此 0 (mod 641)，
即641 。
第一节 同余的基本性质
第一节 同余的基本性质
设式(4)对于n = k成立，则有 1 (mod 2k + 2) = 1 q2k + 2， 其中qZ，所以
=(1 q2k + 2)2=1 q 2k + 31(mod 2k + 3)， 其中q 是某个整数。这说明式(4)当n = k 1也成立。 由归纳法知式(4)对所有正整数n成立。
第一节 同余的基本性质
a2 1 (mod p) pa2 1 = (a 1)(a 1)，
证明 由
pa 1或pa 1，
所以必是
a 1或a 1 (mod p)。
例8 设p是素数，a是整数，则由a2 1(mod p)可以推出
即a 1 (mod p)或a 1 (mod p)。
解 因为792 = 8911，故 792n 8n，9n及11n。 我们有 8n 8 z = 6，
证明 留作习题。
定理5 下面的结论成立： (ⅰ) a b (mod m), dm, d>0 a b (mod d); (ⅱ) a b (mod m), k > 0, kN 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).
定义1 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为 a b (mod m)， 此时也称b是a对模m的同余

数的性质 同余性 同余

则 ≡ ( 1 2 )；
若 ≡ ( 1 )， ≡ ( 2 )，
则 ≡ ( 1 ，2 )。
三、同余的运算性质
3.可约性
（1）若 ≡ ( )， , = 1，则 ≡ ( )
（2）若 ≡ ( )，则 ≡ ( )
（3）若 ≡ ( )，则 ≡ ( )
（4）若 ≡ ( )， , = ，则 ≡ (

)

四、欧拉函数
欧拉函数 ()是定义在正整数上的函数，()表示序列0，1，
2，...， − 1中与互质的整数的个数。



欧拉函数的计算公式：设 = 1 1 2 2 … … ，则
（3）传递性：
Hale Waihona Puke 若 ≡ ( )， ≡ ( )
则 ≡ ( )
三、同余的运算性质
1.可加性
若 ≡ ( )， ≡ ( )
则 + ≡ + ( )
推论
若 + ≡ ( )， ∈ ，
则 ≡ − ( )
() = (1
1
− )
1
(1 −
1
1
) … … (1 − )
2

欧拉定理：设是大于1的整数，（，） = 1，则
() ≡ 1( )
五、典型例题分析
【例1】已知今天是星期三，问1012 后的那一天是星期几？
解：10 ≡ 3( 7)；
1012 ≡ 312 ≡ 274 ≡ −1
三、同余的运算性质
2.可乘性
（1）若 ≡ ( )， ∈ ，则 ≡ ( )
（2）若 ≡ ( )， ≡ ( )，则 ≡ ( )
（3）若 ≡ ( )， ∈ ∗ ，则 ≡ ( )
（4）若 ≡ ( 1 )， ≡ ( 2 )， 1 , 2 = 1，

同余的运算法则

在数论中，同余运算是指两个整数在给定的模数下具有相同的余数。

同余运算有一些重要的性质和法则。

假设a、b 和 c 是整数，n 是正整数。

1. 反身性（Reflexive Property）：a ≡ a（mod n）任何整数与自身在模n 下都是同余的。

2. 对称性（Symmetric Property）：如果a ≡ b（mod n），则b ≡ a（mod n）如果两个整数在模n 下是同余的，那么它们可以互换位置。

3. 传递性（Transitive Property）：如果a ≡ b（mod n）且b ≡ c（mod n），则a ≡ c（mod n）如果两个整数在模n 下与同一个整数是同余的，并且它们之间也是同余的，那么它们之间也是同余的。

运算法则：1. 加法法则：如果a ≡ b（mod n）且c ≡ d（mod n），那么a + c ≡ b + d（mod n）在模n 下，同余的整数的和仍然是同余的。

2. 减法法则：如果a ≡ b（mod n）且c ≡ d（mod n），那么a - c ≡ b - d（mod n）在模n 下，同余的整数的差仍然是同余的。

3. 乘法法则：如果a ≡ b（mod n）且c ≡ d（mod n），那么a * c ≡ b * d（mod n）在模n 下，同余的整数的乘积仍然是同余的。

4. 乘方法则：如果a ≡ b（mod n），那么a^k ≡ b^k（mod n）对于任意正整数k在模n 下，同余的整数的乘方仍然是同余的。

这些法则对于解决同余方程、证明数论中的定理以及在密码学中的应用非常有用。

同余运算也被广泛用于构建哈希函数、加密算法和随机数生成器等领域。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2.1 同余式定义和基本性质
• 由同余的定义, 可得下列性质: （1）自反性: aa (mod m). （2）对称性: 若ab(mod m), 则 ba(mod m). （3）传递性: 若ab(mod m), bc(mod m), 则ac(mod m).
2.1 同余式定义和基本性质
• 同余的性质 若a1b1(mod m), a2b2(mod m), 则: （4） a1 + a2 b1+ b2(mod m). 推论：若a +bc(mod m), 则a c- b(mod m) （5） a1 a2 b1b2(mod m). 推论(Ι) 若ab(mod m)，则akbk(mod m)， 其中k为整数. 推论(Ι Ι)若ab(mod m)，则 an bn(mod m), 其中 n为自然数.
（1）正整数a能被11整除特征是a的奇数位数字和与偶数 位数字和的差能被11整除. （2）正整数a能被11整除特征是a 的末三位数与末三位 数之前的数之差能被11整除.（同理可证7与13也有类 似特征）
自主学习
定理 (弃九法) 若ab=c, 其中a>0, b>0, 并且, p m n i j 则: c ck 10k a ai 10 , b b j 10 ,
2.1 同余式定义和基本性质
• 定义1 给定一正整数m（模）, 若用m去 除两个整数a和b所得余数相同, 则称a 与 b对模m同余, 记作ab(mod m); 若余数 不同, 则称 a 与b对模m不同余, 记作 ab(mod m). 定义2若m|(a-b), 则称a与b对模m同余. 定义3若a= mq+b, 则称a与b对模m同余. 显然，a0(mod m) 等价于 m| a.
2.1 同余式定义和基本性质
（7）若 ac bc(mod m), (m,c)=d, 则 ab(mod m/d). 特别地，当(m,c)=1时，有ab(mod m). （8）若ab(mod m)，则akbk(mod mk)， 其中k为大于零的整数； 若ab(mod m)，d为a,b及 m的任一正公约数, 则 a /d b /d(mod(m/d)) . （9） ab(mod mi), (1≤i≤n), 则ab (mod [m1,m2,…,mn]). （10） 若ab(mod m), 且d|m, 则 ab(modd ).
费马数
当 n 0,1,2,3, 时， Fn 2 2 1 总是素数吗？
n
这个问题是费马在1640年给 梅森的信中宣布的一个猜想。 很容易能证明，前5个费马数都 是素数。到了1732年，数学家 欧拉发现下一个费马数不是素 数，从而否定了费马的猜想。
判断题： 1、若ab(mod m), k为自然数， 则kakb(mod m), kakb(mod km). 反之呢？ 2、若ab(mod m),则a2 b2(mod m). 反之，若a2 b2(mod m)，则ab(mod m)源自专业基础课程初等数论
（二）
Number Theory
第二章 同 余
• 同余是数论中一个基本概念, 它的基本 概念与记号都是伟大的数学家高斯引进 的.它的引人简化了数论中的许多问题. • 本章着重讨论同余的概念及其基本性质， 完全剩余系和简化剩余系，两个重要定 理（欧拉定理和费马小定理）及其应 用．
i 0
j 0
k 0
( a )( b j ) ( Ck )(mod9)
i i 0
m
n
p
.
j 0
k 0
• 可见, 若 ( ai )( b ) ( C )(mod9) j k
m n p i 0 j 0 k 0
,
则可判断乘积ab=c是错误的, 这即是弃九法之 原则：“弃九余不等，计算有问题”.
2.1 同余式定义和基本性质
思考题： 1、整数a是偶数的同余式为( ). 2、整数a是偶数但不能被4整除，则其同余式 为( ). 3、已知a 5(mod6 ) ，则a被3除余( ). 4、已知a 3(mod4 ) ，那么2a+1被4除余( ).
2.1 同余式定义和基本性质
• 例题 例1 有一个大于1的整数，它除300，262，205 所得的余数相同，求这个数。 例2 有兵200余不足300，若1至3报数，最后一 人报数为2，若1至5报数，最后一人报数为2， 若1至7报数，最后一人报数也为2。问这一队 士兵有多少人？ 例3 某天是星期一，从这天后第22012天是星期 几？
2.1 同余式定义和基本性质
例4 分别求3406的个位数字和72012的末两位数字.
例5 证明：641 | 225+1
（欧拉证明了费马数F5不是素数）
例6 （1）求使2n-1能被7整除的一切正整数n； （2）证明：没有正整数n使2n+1能被7整除.
自主学习
特殊数的整除特征 定理 正整数a能被9整除的特征是 a的数字和能 被 9整除. 指出：同理可得到被2（或5）、4（或25）、8 （或125）、3（或9）、11等数整除的特征. 试证：
自主学习
例8 求证 1997×57≠113828. 证明 由于19971＋9＋9＋78 (mod 9) 57 5＋7 3(mod 9) 113828 l+1+3+8+2+8 5(mod 9) • 但是, 8×3=24, 而24≠5(modm 9), 得证. p n i • 注意：使用弃九法时，若 ( a )( b j ) ( Ck )(mod9) i 0 j 0 k 0 也未必肯定原计算是无误的. 例如,：1997×57=113829, 但有人计算结果是 113838，由弃九法可得 24 6(mod 9), 显然, 错误未验证出来.