浅谈同余及其应用

揭阳职业技术学院

毕业论文（设计）

题目：浅谈同余定理及其应用

学生姓名黄指导教师某某某

系（部）师范教育系专业数学教育

班级 999 班学号

提交日期200 年月日答辩日期 200 年月日

200 年月日

浅谈同余定理及其应用

摘要

初等数论是研究数的规律，特别是整数性质的数学分支。它以算术方法为主要研究方法，在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数。同余理论是初等数论中的重要内容之一，其性质及应用研究已引起许多学者的关注。本文归纳总结了同余的若干性质，结合实例，探究了同余性质在检验、判断整除问题、求余数、判断合数、韩信点兵问题等方面的具体应用。体现了用同余性质解决问题的简洁性。

关键词：同余整除余式方程

绪论

初等数论是研究整数性质的一门学科，它是数学中最古老的分支之一，内容极为丰富，曾被数学家说成是数学的皇后。同余问题在当今中小学乃至大学的数学教学中都有涉及，它作为初等数论的核心内容之一，具有很强的应用价值，很多数学问题都要借助同余理论来解决。同余的应用问题分为很多种类型，每种类型的题目又有一定的解题技巧。掌握了这些题型的技巧，可以提高大家解决问题的能力。本文基于对同余理论的理解，将应用同余理论解决的问题具体整理分类，从中分析出一些借助同余理论解题的技巧与规律。现在初等数论中关于同余的内容主要包括：同余的定义及基本性质、剩余类与剩余系、欧拉定理、费马小定理、循环小数、一次同余方程及一次同余方程组。

到目前为止，古今中外很多学者与数学家，对同余的应用问题都有了一定的研究。在中国，早在宋代，大数学家秦九韶所著的《数书九章》中就记载了求解同余方程的“大衍求一术”。还有，著名的古代数学著作《孙子算经》中也记载能解决“物不知其数”问题的孙子定理，也被称作“中国剩余定理”。以及“韩信点兵”问题的研究，都为解决一次同余方程和同余方程组的问题带来了便利。在西方，除了高斯引入同余的概念之外，欧拉和费马提出的定理也为解决同余的相关问题做出了重要的贡献。希望通过本文的研究能将同余理论的应用问题更加系统全面的展现出来。以便，今后大家在探究同余理论时，能对同余应用问题的类型和解决技巧有一个清晰的认识和理解，更好的解决相关问题。

1 相关性质定理[1]

性质1同余是一种等价关系，即有：

（1）反身性 a≡a（mod m）.

（2）对称性若a≡b（mod m），则b≡a（mod m）.

（3）传递性若a≡b（mod m）， b≡c（mod m），

则a≡c（mod m）.

性质2同余式可以相加减,即

若 a≡b（mod m），c≡d（mod m），则

(1) a＋c≡b＋d（mod m）.

(2) a－c≡b－d（mod m）.

性质3同余式可以相乘,即有：

(1) 若a ≡b （mod m ）， c 为自然数, 则ac ≡bc （mod m ）. (2) 若a ≡b （mod m ），c ≡d （mod m ），则ac ≡bd （mod m ）. (3) 若a ≡b （mod m ）， n ≥2, 则a n ≡b n （mod m ）.

性质4 若ac ≡bc （mod m ），且（c ，m ）=1，则

有a ≡b （mod m ）.（其中（c ，m ）表示c 与m 的最大公约数）。

定理1 整数a,b 对模m 同余的充分与必要条件是m ∣a －b ,

即 a ＝b ＋mt. (t 是整数.)

定理2 设a ＝1

1αp 2

2α

p …k

k p α,则

)a （?＝a(1－

11p )(1－21p )…(1－k

p 1

) 定理3 (Euler) 设m 是大于1的整数， (a,m)=1， 则

a )m （?≡1（modm ），其中)m （?为欧拉函数

定理4 (Fermat) 若p 是素数，则a p ≡a （modp ）.

.

证明以上三个定理:

定理1证明: 设 a=mq 1＋r 1, b=mq 2＋r 2, 0≤r 1＜m, 0≤r 2＜m, 若a ≡b （mod m ）, 则r 1=r 2, 因此a －b=m ﹙q 1－q 2﹚.

反之, 若 m | a －b, 则m |m ﹙q 1－q 2﹚＋﹙r 1－r 2﹚,因此 m | r 1－r 2. 又 | r 1－r 2 |＜m ,故r 1=r 2

定理3证明: 设a 1 a 2 … a )m （?, 是modm 的一个简化剩余系， 且（a ,m ）=1,aa 1 aa 2 … aa )m （?也是modm 的一个简化剩余系. a 1 a 2,… a )m （?,≡aa 1 aa 2 … aa )m （? (modm ） ＝a )m （?a 1 a 2 … a )m （?（modm ）. 因此a )m （?≡1（modm ）.

定理4证明: 若（a,p ）＝1,则有a p-1≡a （modp ）,因而a p ≡a （modp ）.若（a,p ）≠1,则p|a ,因而a p ≡0（modp ）, a ≡0（modp ） 故a p ≡a （modp ）

2 同余性质的应用

2.1 求余数问题

2.1.1 利用同余的性质及定理求余数

例1：将从1开始的连续自然数依次写下来，一直写到2003成为一个多位数，123456…20022003，求这个数除以3的余数。

解：由连续的3个自然数的和必能被3整除，而3|2001，（2+0+0+2+2+0+0+3）≡0（mod3）, 所以原多位数除以3余数为0

例2：求201022001被3除所得的非负余数.

解：设201022001=3q＋r, 其中0≤r＜3, 故

r≡201022001（mod3）

且0≤r＜3.又20102=3×670＋2,所以20102≡2(mod3).从而

22001≡22000×2≡41000×2(mod3)

而 22001≡22000×2≡41000×2(mod3),4≡1(mod3)

故 41000≡1 (mod3) ,41000×2≡2 (mod3).

从而 r≡2(mod3). 而0≤r＜3, 故r=2.

即 201022001除以3所得的余数为2.

分析：此类题目解题的关键在于应用同余的乘方性，先求出底数20102对3的余数，再根据性质求出余数的2001次幂对3的余数即可

例3：求437×309×1993被7除的余数。

解：

473≡3（mod7）

309≡1（mod7）

由"同余的可乘性"知：

437×309≡3×1（mod7）≡3（mod7）

又因为1993≡5（mod7）

所以：437×309×1993≡3×5（mod7）

≡15（mod7）≡1（mod7）

即：437×309×1993被7除余1。

分析：此类题目解题的关键在于应用同余的可乘性，分别求出每个因数对于7的余数，在相乘即可简单求出

2.1.2 求星期几问题

求某年某月某日为星期几时,则令D=第N年m月d日,

设D这一天为星期W

D

,

W

D ≡d＋[

5

1

m

13

]＋y＋[

4

y

]＋[

4

c

]＋2c(mod7)

其中c,y 满足N ＝100c ＋y,0≤y ≤100.

注意:算出的结果为1 至7,各代表星期一到星期日.

例:1949年10月1日是星期几?

2.1.3 尾数问题

例1：求243402的末三位数？

解：因为（243，1000）=1，()1000?=1000×﹙1－

21）（1－ 5

1）=400 由欧拉定理知，243400 ≡1（mod1000），故

243402≡2432≡49（mod1000）

所以243402的末三位数为049.

例2：求32001·72002·132003的个位数字？ 解：应用欧拉定理，（3,10）=1,34≡1（mod10）,则有

32001≡34k ＋1≡3（mod10）；

同理，74≡1（mod10）， 72002≡74k ＋2≡9（mod10）； 134≡1（mod10），132003≡134k ＋3≡7（mod10）； 因3×7×9＝189，故个位数字为 9 .

分析：利用同余的性质，求一个数字的个位数字就是求其除以10所得的余数, 同类题型的变换问法：求某数的末两位数字是多少?（模为100）

2.2 同余在检验方面的应用

2.2.1 检查因数的一些方法[1]

方法一： 一整数能被3（9）整除的必要且充分的条件是它的十进位数码的和能被3（9）

整除.

证明：显然我们只须讨论任一正整数a 便可.把a 写成十进位数的形式：

a=a n 10n ＋a n －110n －1＋…＋a 1×10＋a 0 , 0≤a i <10. 因10≡1（mod 3）,故由定理2得a≡a n ＋a n －1＋…＋a 1＋a 0（mod 3）.由已知性质，即知3︱a 当且仅当3︱∑=n

i 0a i .

同法可得9︱a 当且仅当9︱∑=n

i 0

a i

方法二： 设正整数

a=a n 1000n ＋a n －11000n －1＋…＋a 1×1000＋a 0 , 0≤a i <1000.

则7（或11，或13）整除a 的必要且充分的条件是7（或11或13）整除（a 0＋a 2＋…）-（a 1＋a 3＋…）=∑=n

i 0(﹣1)i a i

证明：因为1000与-1对模7（或11或13）同余，故由定理知a 与

∑

=n

i 0

(﹣1)i a i 对

模7（或11或13）同余.由已知性质，7（或11或13） 整除a 当且仅当7（或11或13）整除∑

=n

i 1

(﹣1)i a i

2.2.2 弃九法[1]

（假设我们由普遍乘法的运算方法求出整数a ，b 的乘积是P ，并令 a=a n 10n ＋a n －110n －1

＋…＋a 1×10＋a 0 , 0≤a i <10. b=b m 10m

＋b m －110m －1＋…＋b 1×10＋b 0 , 0≤b j <10. P=c l 10l ＋c l －110l －1＋…＋c 1×10＋c 0 , 0≤c k <10.

我们说：如果（

∑

=n

i 0

a i ）（

∑

=m

j 0

b j ）不同余于∑=l

k c k （mod9），

那么所求得的乘积是错误的.因为

ab≡（∑=n i 0

a i ）（∑=m j 0

b j ）（mod9），P≡ ∑=l

k c k （mod9）.

若 （

∑

=n

i 0

a i ）（

∑

=m

j 0

b j ）不同余于∑=l

k c k （mod9），

则ab 不同余P （mod9）， 故ab 不是P.

2.2.3 判定合数

由费马定理可得推论如下

若p 是素数，且(a,p) ＝1，则a p －1≡1(modp).

利用推论可以判定一个数是否为合数，即若N 是我们要检验的数，先取某一个与N 互素并比N 小的数a ，通常合适的是把a 取为不能整除N 的小素数，如a ＝2, a ＝3或a ＝5……

如果N 是素数那么由推论它应该满足a N －1

≡1(modN)，因此如果验算这个同余不成立，我们就断言 N 是合数.

例2 判断 N ＝117 是否为合数.

分析 我们根据定理3即费马定理，可以考虑若N 是素数， 则有

a N －1≡1(modN)，N 为我们所检验的数.

解：选a=2则a 与N 互素，a N －1=2116=264×232×216×24，

而28

=256≡22(mod117),

216=﹙28)2≡222≡16(mod117)， 232=﹙216)2≡162≡22(mod117)，

264=﹙232)2≡222≡16(mod117)， 故

2116≡264×232×216×24≡16×22×16×16≡32≡1(mod117). 由推论知N 是合数，事实上117＝3×39.

2.3 利用同余的性质解决整除问题

整除问题是数论中的一个重要问题，在初等数学中我们可以直接运用定义和性质解决简单的整除问题，而对于复杂的问题计算则较为麻烦，利用同余良好的性质便可简便的解决复杂的整除问题.

例1 求证1985|3237n－632n－855n＋235n,n∈N﹢.

分析记A=3237n－632n－855n＋235n, n∈N﹢,

由于1985=5×397,所以

1985|A?A≡0(mod1985)?A≡0 (mod5), A≡0 (mod397)

证明记A=3237n－632n－855n＋235n,n∈N﹢,

根据定理1只要证明A≡0 (mod1985) 即可，

由于1985=5×397，故只要证明A≡0(mod5) 和A≡0(mod397) 成立. 事实上，由于3237≡2(mod5),632≡2(mod5),855≡0(mod5),235≡0(mod5),

根据性质3，?n∈N﹢,则有

3237n ≡2n(mod5),632n≡2n(mod5), 855n≡0(mod5), 235n≡0(mod5),所以

A≡2n－2n－0＋0≡0(mod5).

又由于3237≡61(mod397), 632≡235(mod397),

855≡61(mod397), 235≡235(mod397),

根据性质3, n∈N﹢我们有

3237n≡61n(mod397), 632n≡235n(mod397),

855n≡61n(mod397), 235n≡235n(mod397),

所以

A≡61n－235n－61n＋235n≡0(mod397).

又因为(5,397)≡1，所以A≡0(mod5×397),即A≡0(mod1985). 根据同余整除

关系知?n∈N﹢,必有1985|A,即

1985|3237n－632n－855n＋235n

3.3 中国古代同余问题

3.3.1 中国剩余问题[2]《孙子算经》卷下“物不知数”

题说：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？

显然，这相当于求不定方程组

N=3x+2，N=5y+3，N=7z+2 的正整数解N，

或用现代数论符号表示，等价于解下列的一次同余组：

N≡ 2(mod3) N≡3(mod5) N≡2(mod7)②

《孙子算经》所给答案是N＝23。

3.3.2 韩信点兵问题

曰:有兵一队,若列成五行纵队,则末行一人,成六行纵队,则末行五人,成七行纵队,则末行四人,成十一行纵队,则末行十人,求兵数.

解:由题意有x≡1(mod5), x≡5(mod6), x≡4(mod7), x≡10(mod11)

求得x≡2111（2310）

同余理论是初等数论中最核心的内容之一，由同余定义可知，若a≡b(modm)，则 a 和 b被 m除后有相同的余数。这里m 为正整数，一般要求 m大于1，称为模，同余这一思想本质上是将整数按模m 分类，然后讨论每一个类中整数所具有的共性及不同类之间的差异。从同余的定理上看，同余和整除实际上是同一回事，故同余还有两个等价的定义：①用整除来定义即m∣a-b。②用等号来定义a=b+mt。值得注意a和 b关于m同余个相对的概念。即它是相对于模 m来讲，两个整数 a和 b关于一个整数模m 同余。则对于另一个整数模m

，a 和 b未必会同余。

i

参考文献

[1]闵嗣鹤、严士健：《初等数论》,高等教育出版社，2003年第三版。

[2] 《孙子算经》,下卷第26题.

揭阳职业技术学院毕业论文（设计）指导进度表

揭阳职业技术学院毕业论文（设计）成绩评定表

浅谈留数及其应用

浅谈留数及其应用 徐松松41345053 计1304 1. 留数 留数是复变函数论中重要的概念之一，它与解析函数在孤立奇点处的洛朗展开式、柯西复合闭路定理等都有密切的联系. （1） 留数的概念及留数定理 定义5.4 设0z 是解析函数)(z f 的孤立奇点，我们把)(z f 在0z 处的洛朗展 开式中负一次幂项的系数1-C 称为)(z f 在0z 处的留数.记作]),([Re 0z z f s ，即]),([Re 0z z f s =1-C .显然，留数1-C 就是积分 dz z f i C ?)(21π的值，其中C 为解析函数)(z f 的0z 的去心邻域内绕0z 的闭曲线. 关于留数，我们有下面定理. 定理5.7（留数定理） 设函数)(z f 在区域D 内除有限个孤立奇点 n z z z z ,,,,321 外处处解析，C 是D 内包围各奇点的一条正向简单闭曲线，那么∑?==n k k C z z f s i dz z f 1]),([Re 2)(π. 一般来说，求函数在其孤立奇点0z 处的留数只须求出它在以0z 为中心的圆环域内 的洛朗级数中101---）（z z C 项系数1-C 就可以了.但如果能先知道奇点的类型，对求留数 更为有利.例如，如果0z 是)(z f 的可去奇点，那么0]),([Re 0=z z f s .如果0z 是本性奇点，那就往往只能用把)(z f 在0z 展开成洛朗级数的方法来求1-C .若0z 是极点的情形，则可用较方便的求导数与求极限的方法得到留数. （2） 函数在极点的留数 法则1：如果0z 为)(z f 的简单极点，则 )()(lim ]),([Re 000 z f z z z z f s z z -=- （5.4） 法则2：设) ()()(z Q z P z f =，其中)(,)(z Q z P 在0z 处解析，如果0)(≠z P ，0z 为)(z Q 的一阶零点，则0z 为)(z f 的一阶极点，且 ) ()(]),([Re 0z Q z P z z f s '=. （5.5）

浅谈同余及其应用

揭阳职业技术学院 毕业论文（设计） 题目：浅谈同余定理及其应用 学生姓名黄指导教师某某某 系（部）师范教育系专业数学教育 班级 999 班学号 11211211 提交日期200 年月日答辩日期 200 年月日 200 年月日

浅谈同余定理及其应用 摘要 初等数论是研究数的规律，特别是整数性质的数学分支。它以算术方法为主要研究方法，在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数。同余理论是初等数论中的重要内容之一，其性质及应用研究已引起许多学者的关注。本文归纳总结了同余的若干性质，结合实例，探究了同余性质在检验、判断整除问题、求余数、判断合数、韩信点兵问题等方面的具体应用。体现了用同余性质解决问题的简洁性。 关键词：同余整除余式方程

绪论 初等数论是研究整数性质的一门学科，它是数学中最古老的分支之一，内容极为丰富，曾被数学家说成是数学的皇后。同余问题在当今中小学乃至大学的数学教学中都有涉及，它作为初等数论的核心内容之一，具有很强的应用价值，很多数学问题都要借助同余理论来解决。同余的应用问题分为很多种类型，每种类型的题目又有一定的解题技巧。掌握了这些题型的技巧，可以提高大家解决问题的能力。本文基于对同余理论的理解，将应用同余理论解决的问题具体整理分类，从中分析出一些借助同余理论解题的技巧与规律。现在初等数论中关于同余的内容主要包括：同余的定义及基本性质、剩余类与剩余系、欧拉定理、费马小定理、循环小数、一次同余方程及一次同余方程组。 到目前为止，古今中外很多学者与数学家，对同余的应用问题都有了一定的研究。在中国，早在宋代，大数学家秦九韶所著的《数书九章》中就记载了求解同余方程的“大衍求一术”。还有，著名的古代数学著作《孙子算经》中也记载能解决“物不知其数”问题的孙子定理，也被称作“中国剩余定理”。以及“韩信点兵”问题的研究，都为解决一次同余方程和同余方程组的问题带来了便利。在西方，除了高斯引入同余的概念之外，欧拉和费马提出的定理也为解决同余的相关问题做出了重要的贡献。希望通过本文的研究能将同余理论的应用问题更加系统全面的展现出来。以便，今后大家在探究同余理论时，能对同余应用问题的类型和解决技巧有一个清晰的认识和理解，更好的解决相关问题。 1 相关性质定理[1] 性质1同余是一种等价关系，即有： （1）反身性 a≡a（mod m）. （2）对称性若a≡b（mod m），则b≡a（mod m）. （3）传递性若a≡b（mod m）， b≡c（mod m）， 则a≡c（mod m）. 性质2同余式可以相加减,即 若 a≡b（mod m），c≡d（mod m），则 (1) a＋c≡b＋d（mod m）. (2) a－c≡b－d（mod m）. 性质3同余式可以相乘,即有：

余数性质及同余定理(B级) 1

一、 带余除法的定义及性质 1. 定义：一般地，如果a 是整数，b 是整数（b ≠0）,若有a ÷b =q ……r ，也就是a ＝b ×q ＋r , 0≤r ＜b ；我们称上面的除法算式为一个带余除法算式。这里： (1)当0r =时：我们称a 可以被b 整除，q 称为a 除以b 的商或完全商 (2)当0r ≠时：我们称a 不可以被b 整除，q 称为a 除以b 的商或不完全商 一个完美的带余除法讲解模型:如图 这是一堆书，共有a 本，这个a 就可以理解为被除数，现在要求按照b 本一捆打包，那么b 就是除数的角色，经过打包后共打包了c 捆，那么这个c 就是商，最后还剩余d 本，这个d 就是余数。 这个图能够让学生清晰的明白带余除法算式中4个量的关系。并且可以看出余数一定要比除数小。 2. 余数的性质 ⑴ 被除数=除数?商+余数；除数=（被除数-余数）÷商；商=（被除数-余数）÷除数； ⑵ 余数小于除数． 二、 余数定理： 1.余数的加法定理 a 与 b 的和除以 c 的余数，等于a ,b 分别除以c 的余数之和，或这个和除以c 的余数。 例如：23，16除以5的余数分别是3和1，所以23+16＝39除以5的余数等于4，即两个余数的和3+1. 当余数的和比除数大时，所求的余数等于余数之和再除以c 的余数。 例如：23，19除以5的余数分别是3和4，所以23+19＝42除以5的余数等于3+4=7除以5的余数为 2 2.余数的加法定理 a 与 b 的差除以 c 的余数，等于a ,b 分别除以c 的余数之差。 知识框架 余数性质及同余定理

例如：23，16除以5的余数分别是3和1，所以23－16＝7除以5的余数等于2，两个余数差3－1＝ 2. 当余数的差不够减时时，补上除数再减。 例如：23，14除以5的余数分别是3和4，23－14＝9除以5的余数等于4，两个余数差为3＋5－4＝4 3.余数的乘法定理 a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。 例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1＝3。当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。 例如：23，19除以5的余数分别是3和4，所以23×19除以5的余数等于3×4除以5的余数，即2. 乘方：如果a与b除以m的余数相同，那么n a与n b除以m的余数也相同． 一、同余定理 1、定义 整数a和b，除以一个大于1的自然数m所得余数相同，就称a和b对于模m同余或称a和b在模m下同余，即a≡b（modm） 2、同余的重要性质及举例。 〈1〉a≡a（modm）（a为任意自然）； 〈2〉若a≡b（modm），则b≡a（modm） 〈3〉若a≡b（modm），b≡c（modm）则a≡c（modm）； 〈4〉若a≡b（modm），则ac≡bc（modm） 〈5〉若a≡b（modm），c≡d（modm），则ac=bd（modm）； 〈6〉若a≡b（modm）则an≡bm（modm） 其中性质〈3〉常被称为"同余的可传递性"，性质〈4〉、〈5〉常被称为"同余的可乘性，"性质〈6〉常被称为"同余的可开方性" 注意：一般地同余没有"可除性"，但是：如果：ac=bc（modm）且（c，m）=1则a≡b（modm）3、整数分类： 〈1〉用2来将整数分类，分为两类： 1，3，5，7，9，……（奇数）； 0，2，4，6，8，……（偶数） 〈2〉用3来将整数分类，分为三类： 0，3，6，9，12，……（被3除余数是0） 1，4，7，10，13，……（被3除余数是1） 2，5，8，11，14，……（被3除余数是2）

同余的性质与应用

. 1 同余的性质及应用 1 引言 数论的一些基础容的学习，一方面可以加深对数的性质的了解，更深入的理解某些其他邻近学科，另一方面，可以加强数学训练.而整数论知识是学习数论的基础，其中同余理论有时整数论的重要组成部分，所以学好同余理论是非常重要的. 在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数，例如我们问现在是几点钟，就是用24去除某一个总的时数所得的余数；问现在是星期几，就是问用7去除某一个总的天数所得的余数，假如某月2号是星期一，用7去除这月的号数，余数是2的都是星期一. 我国古代子算经里已经提出了同余式11(mod )xb m ,22(mod )xb m ,…, (mod )k k xb m 这种形式的问题，并且很好地解决了它.宋代大数学家九韶在他的《数学九章》中提出了同余式1(mod )i i x M m ≡, 1,2,...,i k =, i m 是k 个两两互质的正整数， 12...k m m m m =,i i m m M =的一般解法. 同余性质在数论中是基础，许多领域中一些著名的问题及难题都是利用同余理论及一些深刻的数学概念，方法，技巧求解.例如，数论不定方程中的费尔马问题，拉格朗日定理的证明堆垒数论中的华林问题，解析数论中，特征函数基本性质的推导等等.在近现代数论研究中，有关质数分布问题，如除数问题，圆格点问题，等差级数问题中的质数分布问题，2an bn c ++形式的质数个数问题，质数个数问题，质数增大的快慢问题，孪生质数问题都有一定程度的新成果出现，但仍有许多尚未解决的问题. 数论的发展以及现代数学发展中提出的一些数论问题，都要求我们对于近代数论的一些方法和基础知识，必须熟练掌握.所以，本文主要介绍了同余理论中同余基本性

【小学六年级奥数】第38讲 应用同余问题

第38讲应用同余问题 一、知识要点 同余这个概念最初是由伟大的德国数学家高斯发现的。同余的定义是这样的： 两个整数a，b，如果它们除以同一自然数m所得的余数想同，则称a，b对于模m同余。记作：a≡b（mod ｍ）。读做：ａ同余于ｂ模ｍ。比如，12除以5，47除以5，它们有相同的余数2，这时我们就说，对于除数5，12和47同余，记做12≡47（mod 5）。 同余的性质比较多，主要有以下一些： 性质（1）：对于同一个除数，两个数之和（或差）与它们的余数之和（或差）同余。比如：32除以5余数是2，19除以5余数是4，两个余数的和是2+4=6。“32+19”除以5的余数就恰好等于它们的余数和6除以5的余数。也就是说，对于除数5，“32+19”与它们的余数和“2+4”同余，用符号表示就是：32≡2（mod 5），19≡4（mod 5），32+19≡2+4≡1（mod 5） 性质（2）：对于同一个除数，两个数的乘积与它们余数的乘积同余。 性质（3）：对于同一个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。 性质（4）：对于同一个除数，如果两个整数同余，那么它们的乘方仍然同余。 应用同余性质几萼体的关键是要在正确理解的基础上灵活运用同余性质。把求一个较大 1

的数除以某数的余数问题转化为求一个较小的数除以这个数的余数，使复杂的题变简单，使困难的题变容易。 二、精讲精练 【例题1】求1992×59除以7的余数。 应用同余性质（2）可将1992×59转化为求1992除以7和59除以7的余数的乘积，使计算简化。1992除以7余4，59除以7余3。根据同余性质，“4×3”除以7的余数与“1992×59”除以7的余数应该是相同的，通过求“4×3”除以7的余数就可知道1992×59除以7的余数了。 因为1992×59≡4×3≡5（mod 7） 所以1992×59除以7的余数是5。 练习1： 1、求4217×364除以6的余数。 2、求1339655×12除以13的余数。 2

余数性质及同余定理(B级)

一、 带余除法的定义及性质 1. 定义：一般地，如果a 是整数，b 是整数（b ≠0）,若有a ÷b =q ……r ，也就是a ＝b ×q ＋r , 0≤r ＜b ；我们称上面的除法算式为一个带余除法算式。这里： (1)当0r =时：我们称a 可以被b 整除，q 称为a 除以b 的商或完全商 (2)当0r ≠时：我们称a 不可以被b 整除，q 称为a 除以b 的商或不完全商 一个完美的带余除法讲解模型:如图 这是一堆书，共有a 本，这个a 就可以理解为被除数，现在要求按照b 本一捆打包，那么b 就是除数的角色，经过打包后共打包了c 捆，那么这个c 就是商，最后还剩余d 本，这个d 就是余数。 这个图能够让学生清晰的明白带余除法算式中4个量的关系。并且可以看出余数一定要比除数小。 2. 余数的性质 ⑴ 被除数=除数?商+余数；除数=（被除数-余数）÷商；商=（被除数-余数）÷除数； ⑵ 余数小于除数． 一、 余数定理： 1.余数的加法定理 a 与 b 的和除以 c 的余数，等于a ,b 分别除以c 的余数之和，或这个和除以c 的余数。 例如：23，16除以5的余数分别是3和1，所以23+16＝39除以5的余数等于4，即两个余数的和3+1. 当余数的和比除数大时，所求的余数等于余数之和再除以c 的余数。 例如：23，19除以5的余数分别是3和4，所以23+19＝42除以5的余数等于3+4=7除以5的余数为 2 2.余数的加法定理 a 与 b 的差除以 c 的余数，等于a ,b 分别除以c 的余数之差。 例如：23，16除以5的余数分别是3和1，所以23－16＝7除以5的余数等于2，两个余数差3－1＝ 2. 当余数的差不够减时时，补上除数再减。 余数性质及定理 知识框架

浅析中国剩余定理及其应用

浅析中国剩余定理及其应用 李辉 （井冈山学院数理学院信息与计算科学 343009） 指导老师颜昌元 [摘要]：本文阐述了中国剩余定理的由来，介绍了它的几种解法，及其它在多项式，现代密码学，生活方面的应用. [关键词]：中国剩余定理；解法;多项式；现代密码学 引言在中国,以剩余定理为代表的同余理论源远流长,可追溯到《周易》中的卜筮古法.秦九韶说:“圣有大衍,微寓于《易》”,即指此意.另外,同余理论的另一个来源是古代制定历法的需要.实际上,从汉末到宋末1000余年的时间中,有很多天文学家熟悉一次同余式的解法,他们在编制历法时利用它来推算“上元积年”.中国剩余定理对现代数学的研究有很强的启迪意义.特别是在多项式，密码学中的应用非常关键. 一中国剩余定理的由来 我国古代《孙子算经》中有一著名而又重要的问题:“今有物不知其数,三三数之剩二、五五数之剩三,七七数之剩二,问物几何.答曰:二十三”.这一问题可译为:一个数除以3余2,除以5余3,除以7余2.求适合条件的最小的数.题中还介绍了它的解法:“术曰:三三数之剩二,置一百四十;五五数之剩三,置六十三;七七数之剩二,置三十;并之,得二百三十三,以二百十减之,即得.”意即:物数W=70×2+21×3+15×2-2×105=23.接下来又给出了这类题的一般解法(余数为一的情况):术文说:“凡三三数之剩一,则置七十;五五数之剩一,则置二十一;七七数之剩一,则置十五.一百六以上,以一百五减之,即得.”这个问题及其解法,在世界数学史上占有重要的地位,因此,中外数学家都尊称为“孙子定理”或“中国剩余定理”. 为了比较清楚地了解“中国剩余定理”这一名称的由来,我们不妨先引进同余定义:一般地,若两个整数a、b被同一个大于1的整数m除有相同的余数,那么称a、b对于模m同余.记作: a≡b (mod m）应用同余原理,我们把“物不知其数”问题用整数的同余式符号表达出来,是:设N≡2 (mod 3)≡3 (mod 5)≡2 (mod 7),求最小的数N.答案是N=23. 书中问题及其解法,建立起数学模型就是: 设a、b、c为余数, P为整数,则N≡a(mod 3)≡b(mod 5)≡c(mod 7) 的解是: N=70a+21b+15c-105P (1) 现在,我们把上述解法中的a,b,c作一分析:设M=3×5×7,则 70=2×5×7=2×(3×5×7)/3=2×M/3

同余的应用的开题报告

呼伦贝尔学院 本科生毕业论文开题报告题目同余的应用 专业数学与应用数学 姓名______________________彭丽霞 学号2011071115 指导教师付莉 2014年11月7日

七、论文提纲 （一）前言 同余是《算术研究》中的一个基本研究课题，这个术语来自拉丁文，同余的概念的建立和同余符号的引入大大简化了数论中的许多问题，它的引入使得无限的整数被划分为有限类。而且同余在生产、生活中也有广泛的应用，如制作万年历、循环赛程、电话电缆的 （二）提纲 一、同余 1、同余的定义 2、同余的定理 3、同余的性质 4、完全剩余系定义 5、完全剩余系定理 6、一次同余式定义 7、孙子定理 二、同余的应用 1、求最大公约数 2、检验因子 3、检验整数计算 4、检验素数合数 5、循环赛程 6、万年历 （三）结论 通过本文的论证，我们发现同余的出现给很多问题的解决提供了简便的途径。同余的性质虽然只有固定的那几条，但它却能解决许多困扰我们的问题，在解决问题时开阔了我们的思路。同余的性质易懂，但在运用其解题时有一定的困难，所以在生活中我们要仔细观察。 八、参考文献 [1]苏亚丽，杨继明.孙子定理在两个数学竞赛题的应用[J].云南：玉溪师范学院学报（第27卷），2011年第4期. [2]郭小菊.同余法求最大公约数[J].读与写杂志，2012，4. [3]潘承洞，潘承彪.初等数论[M]北京大学出版社，1992. [4]刘合义.谈数论中的同余及其应用[J].河北：衡水师范专科学校.第4卷，第11期，2002， [5]姜浩瑞.初等数论在高中数学解题中的一些应用[J].中学数学教学，2006，第5期. [6]姚磊.整除性的若干解法[J].皖西学院学报2001，5 [7]王志兰.关于同余的几个问题[J].高师理科学刊.2009，28(5)：44—46 [8]颜松远.数论及应用[J]数学实践与认知，2002，19(4)：486—508 [9]原新生.一次同余方程的几种解法[J].牡丹江教育学院学报，2009，115(3)：115 [10]陈小辉.关于同余理论在中学奥数中的应用[J].数学通讯，2001，(5)：43—46

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 ≡-

(完整版)复变函数第六章留数理论及其应用知识点总结

第六章留数理论及其应用 §1.留数 1.（定理6.1 柯西留数定理）： ∫f(z)dz=2πi∑Res(f(z),a k) n k=1 C 2.（定理6.2）：设a为f(z)的m阶极点， f(z)= φ(z) (z?a)n , 其中φ(z)在点a解析，φ(a)≠0，则 Res(f(z),a)=φ(n?1)(a) (n?1)! 3.（推论6.3）：设a为f(z)的一阶极点， φ(z)=(z?a)f(z),则 Res(f(z),a)=φ(a) 4.（推论6.4）：设a为f(z)的二阶极点 φ(z)=(z?a)2f(z)则 Res(f(z),a)=φ′(a) 5.本质奇点处的留数：可以利用洛朗展式 6.无穷远点的留数： Res(f(z),∞)= 1 2πi ∫f(z)dz Γ? =?c?1 即，Res(f(z),∞)等于f(z)在点∞的洛朗展式中1 z 这一项系数的反号 7.（定理6.6）如果函数f(z)在扩充z平面上只有有限个孤立奇点（包括无穷远点在内），设为a1,a2,…,a n,∞,则f(z)在各点的留数总和为零。 注：虽然f(z)在有限可去奇点a处，必有Res(f(z),∞)=0，但是，如果点∞为f(z)的可去奇点（或解析点），则Res(f(z),∞)可以不为零。 8.计算留数的另一公式：

Res (f (z ),∞)=?Res (f (1t )1t 2,0) §2.用留数定理计算实积分 一.∫R (cosθ,sinθ)dθ2π0型积分 → 引入z =e iθ 注：注意偶函数 二.∫P(x)Q(x)dx +∞?∞型积分 1.（引理6.1 大弧引理）：S R 上 lim R→+∞zf (z )=λ 则 lim R→+∞∫f(z)dz S R =i(θ2?θ1)λ 2.（定理6.7）设f (z )=P (z )Q (z )为有理分式，其中 P (z )=c 0z m +c 1z m?1+?+c m (c 0≠0) Q (z )=b 0z n +b 1z n?1+?+b n (b 0≠0) 为互质多项式，且符合条件： （1）n-m ≥2; （2）Q(z)没有实零点 于是有 ∫ f (x )dx =2πi ∑Res(f (z ),a k )Ima k >0 +∞ ?∞ 注：lim R→R+∞ ∫f(x)dx +R ?R 可记为P.V.∫f(x)dx +∞?∞ 三. ∫P(x)Q(x)e imx dx +∞?∞ 型积分 3.（引理6.2 若尔当引理）：设函数g(z)沿半圆周ΓR :z =Re iθ(0≤θ≤π，R 充分大)上连续，且 lim R→+∞g (z )=0 在ΓR 上一致成立。则 lim R→+∞ ∫g(z)e imz dz ΓR =0 4.（定理6.8）：设g (z )=P (z )Q (z )，其中P(z)及Q(z)为互质多项式，且符合条件：

15、同余法解题

第十五讲同余法解题 一、知识要点 在平时解题中，我们经常会遇到把着眼点放在余数上的问题。如：现在时刻是7时30分，再过52小时是几时几分？我们知道一天是24小时，52÷24=2……4，也就是说52小时里包含两个整天再加上4小时，这样就在7时30分的基础上加上4小时，就是11时30分。很明显这个问题的着眼点是放在余数上了。 1、同余的表达式和特殊符号:37和44同除以7，余数都是2，把除数7称作“模7”，37、44对于模7同余。记作：37≡44(mod7),“≡”读作同余。一般地，两个整数A 和B，除以大于1的自然数M所得的余数相同，就称A、B对于模M同余，记作：A≡B(modM) 2、同余的性质 （1）A≡A(modM)（每个整数都与自身同余，称为同余的反身性。） （2）若A≡B(modM)，那么B≡A(modM)（这称作同余的对称性） （3）若A≡B(modM)，B≡C(modM)，则A≡C(modM)（这称为同余的传递性） （4）若A≡B(modM)，C≡D(modM)，则A±C≡B±D(modM)（这称为同余的可加性、可减性）则A×C≡B×D(modM)（称为同余的可乘性） （5）若A≡B(modM)，则A n≡B n (modM)，n为正整数，同余还有一个非常有趣的现象：如果A≡B(modM),那么M｜(A－B)（A－B的差一定能被M整除）,这是为什么呢？ 3、同余口诀：“差同减差，和同加和，余同取余，最小公倍加”这是同余问题的口诀。1）、差同减差：用一个数除以几个不同的数，得到的余数，与除数的差相同，此时反求的这个数，可以选除数的最小公倍数，减去这个相同的差数，称为：“差同减差”。例：“一个数除以4余1，除以5余2，除以6余3”，因为4-1=5-2=6-3=3，所以取-3，表示为60n-3。 2）、和同加和：用一个数除以几个不同的数，得到的余数，与除数的和相同，此时反求的这个数，可以选除数的最小公倍数，加上这个相同的和数，称为：“和同加和”。例：“一个数除以4余3，除以5余2，除以6余1”，因为4+3=5+2=6+1=7，所以取+7，表示为60n+7。 3）、余同取余：用一个数除以几个不同的数，得到的余数相同，此时反求的这个数，可以选除数的最小公倍数，加上这个相同的余数，称为：“余同取余”。例：“一个数除以4余1，除以5余1，除以6余1”，因为余数都是1，所以取+1，表示为60n+1。

4.1基本概念及一次同余式

1. 同余方程15x ≡12(mod99)关于模99的解是__ x ≡14,47,80(mod99)_。 2. 同余方程12x+7≡0 (mod 29)的解是__ x ≡26 (mod 29)_____. 3. 同余方程41x≡3(mod 61)的解是__ _ . 4. 同余方程9x+12≡0(mod 37)的解是___ x ≡11(mod 37)______ 5. 同余方程13x ≡5(mod 31)的解是_ x ≡ 29(mod 31)__ 6. 同余方程24x ≡6(mod34)的解是__ x ≡13,30(mod34)__ 7. 同余方程26x+1≡33 (mod 74)的解是__ x ≡24,61 (mod 74)_ 8. 同余方程ax +b ≡0(mod m )有解的充分必要条件是__()b m a ,_ 9. 21x ≡9 (mod 43)的解是_ x ≡25 (mod 43)__ 10. 设同余式()m b ax mod ≡有解()m x x mod 0≡，则其一切解可表示为_ _ . 11. 解同余式()15mod 129≡x 12. 同余式()111mod 1227≡x 关于模11有几个解？（ ） A 1 B 2 C 3 D 4 13. 同余式3x ≡2(mod20)解的个数是（ B ） A.0 B.1 C.3 D.2 14. 同余式72x ≡27(mod81)的解的个数是_9_个。 15. 同余方程15x ≡12(mod27) 16. 同余方程6x ≡4(mod8)有 个解。 17. 同余式28x ≡21(mod35)解的个数是( B ) A.1 B.7 C.3 D.0 18. 解同余方程：63x ≡27(mod72) 19. 同余方程6x≡7(mod 23)的解是__ _ . 20. 以下同余方程或同余方程组中,无解的是（ B ） A.6x ≡10(mod 22) B.6x ≡10(mod 18) C.???≡≡20) 11(mod x 8) 3(mod x D. ???≡≡9) 7(mod x 12) 1(mod x 21. 同余方程12x ≡8(mod 44)的解是x ≡8,19,30,41(mod 44)____ 22. 同余方程20x ≡14(mod 72)的解是 ___ 23. 下列同余方程无解的是( A ) A.2x ≡3(mod6) B.78x ≡30(mod198) C.8x ≡9(mod11) D.111x ≡75(mod321) 24. 解同余方程 17x+6≡0(mod25) 25. 同余方程3x ≡5(mod16) 的解是___ x ≡7(mod16)____ 26. 同余方程3x ≡5(mod14)的解是_ x ≡11(mod14)的解是__。 27. 同余方程3x ≡5(mod13)的解是__ x ≡6(mod13)_________。 28. 下列同余方程有唯一解的是( C )

幂同余定理及其应用

幂同余定理及其应用 吴敏金mjwu1940@https://www.sodocs.net/doc/746626546.html, 由同余式的性质，可推出 [幂同余定理] 设同余式a==b (mod m)，那么对于任意的正整数n, a^n==b^n (mod m).。（^n表示n次方，==表示同余）证明： 由同余式的性质，如果a==b (mod m)，c==d (mod m)，则a*c==b*d (mod m)。 取c=a, d=b，作n次乘法即得结论。证毕 幂同余定理可应用于幂同余方程求解： 对于给定的m,n，已知a，求a^n==x (mod m)，(0<=x

所以，13^2015除以170的余数为155。 由上面2例可见，利用幂同余定理 比直接计算3^2015，13^2015方便得多了。 下面示例，给出当a>m时的求解方法。 3，求23^5555除以7的余数？ 解：由23==2 (mod 7), 及8==1 (mod7) 23^5555==2^5555==(2^3)^1851*4==1^1851*4==4 (mod 7) 所以，23^5555除以7的余数为4。 对于另一类幂同余方程：对于给定的m,n，已知b, 求x^n==b (mod m)。较为复杂，另文讨论。

小学奥数同余问题

同余问题（一） 在平时解题中，我们经常会遇到把着眼点放在余数上的问题。如：现在时刻是7时30分，再 过52小时是几时几分？我们知道一天是24小时，少一二二：……-，也就是说52小时里包含两个整天再加上4小时，这样就在7时30分的基础上加上4小时，就是11时30分。很明显这个问题的着眼点是放在余数上了。 1. 同余的表达式和特殊符号 37和44同除以7,余数都是2,把除数7称作“模7”，37、44对于模7同余。 记作：（mod7 “三”读作同余。 一般地，两个整数a和b，除以大于1的自然数m所得的余数相同，就称a、b对于模m同余, 记作.，一〔r ■ 2. 同余的性质 （1）-，-?:丄-「一（每个整数都与自身同余，称为同余的反身性。） （2）若’一：°"，那么- 一n ‘ （这称作同余的对称性） （3）若:V，贝U - ■■■.（这称为同余的传递性）（4）若r- ': 1'：，—「—，，贝U丄―二-（一"）（这称为同余的可加性、可减性） 1- 」（称为同余的可乘性） （5）若'-:-1-'-- ° ,则r ；- T'■- :，n为正整数，同余还有一个非常有趣的现象： 如果詔 -：1- ■- '■- 那么日瑤严的差一定能被k整除） 这是为什么呢？ ? d；- 上） a=充7〕4鬥 盘一B =切［+ 口一（舫2 +与） 二切-切-金） k也就是■二的公约数，所以有…一- ■ k\（a -町 下面我们应用同余的这些性质解题。 【例题分析】 例1.用412、133和257除以一个相同的自然数，所得的余数相同，这个自然数最大是几？

分析与解答： 假设这个自然数是a,因为412、133和257除以a所得的余数相同，所以诃(412-1羽，，|(412?笳6讷化57-1辺， 说明a是以上三个数中任意两数差的约数，要求最大是几，就是求这三个差的最大公约数。 (巧5, 124, 279) =31 所以a最大是31 o 例2. 除以19,余数是几？ 分析与解答： 如果把三个数相乘的积求出来再除以19，就太麻烦了，利用同余思想解决就容易了。 249.2(uodl9) 388 = 8(mod 19) 234要乳m初19) 234x 388x249 = 6x8x2(mod!93 6x8x2 = 所以一 I .： 1.： 此题应用了同余的可乘性，同余的传递性。 222 (2) ' ------ V ------ ' 例3.有一个1997位数，它的每个数位都是2，于；这个数除以13,商的第100位是几？最后余数是几？ 分析与解答： 222 (2) 吃这个数除以13,商是有规律的。 222 (2) 、-- V------- ' 1997个2 亠13= 170940170940... 商是170940六个数循环，那么1 -：1- - - = 1 - ....... 4 ,即"1_4 1'.，我们从左向右数“ 170940'的第4个数就是 我们找的那个数“ 9”，所以商的第 100位是9o 余数是几呢？ 222 (2) ' ----- V ------ ' ? 199亍个2 -^13 = 170^40170940.... 1995^ 6= 332 (4) 则'丄「」_ 所以商的个位数字应是“ 170940'中的第 4个，商应是9,相应的余数是5 【模拟试题】(答题时间：20分钟) 1. 求下列算式中的余数。 111......1 222 (2)

第十八讲同余问题

第18次 同余问题 一、知识要点和基本方法 14和26这两个数虽然大小不同，但它们分别除以6所得的余数相同，我们把14和26叫做关于模6同余，记作14 ≡26（mod6）．同余最基本的性质是：几个同余式（模相同）相加、减、乘、乘方仍然同余．应用同余性质，可以很简便地求一些较大算式或数除以某个自然数的余数． 有一些数学问题，与数的大小关系不大，而主要与这个数除以某数的余数有关．例如，自然数的个位数字，实际上就是这个自然数除以10的余数．还有一些数学问题，是要解决一些周期性变化的数字问题，这里不—一列举．利用同余性质，可以巧妙地解决上述的这些问题． 二、例题精讲 例11991和1769除以某一个自然数n，余数分别为2和l，那么n最小是多少？ 解1991－2＝1989能被n整除，同理1769－1＝1768也能被这个数n整除．所以n是1989与1768的最大公约数的约数，且应大于2． 因为（1989，1768）＝13 × 17，所以n最小是13． 例2把由1开始的自然数依次写下来，直写到第201位为止，这个数除以3的余数是几？ 解把由1开始的自然数依次写下来，直写到第201位为止，一位数写了1 ×9＝9（个）数码，两位数写了2 ×90＝180（个）数码，5位数写了（201－9＝180）÷3＝4（个），即写到了99＋4＝103，因此由1开始的自然数依次写下来的201位数是由1开始的103个连续自然数组成的．经过观察发现，不论从哪开始，每连续3个自然数的各位上数字的和能被3整除．因为一共是103个自然数，所以103 ÷3＝34……l，前102个自然数（3 ×34＝102）的各位上数字之和都能被3整除，而201位数的最后三位数是103，所以： 103 ÷ 3＝34……1，即这个201位数除以3余数是1． 例3除以3余l，除以5余已除以7余4的最小三位数是几？ 解因为除以3余l，除以5余2的最小数是22，而3和5的最小公倍数是15，所以符合条件的数可以是22，37，52，67，…．又因为67 ÷7＝9……4，所以67是符合题中三个条件的最小数，而3，5和7的最小公倍数是105，这样符合条件的数有67，172，277，…． 所以，符合条件的最小三位数是172． 例4有1991个9组成的多位数999…99除以74所得的余数是多少？ 解因为9 999 ÷74＝135......9，即135 × 74＝9 990，这说明凡是9 990 (00) 形式的数均能被74整除，而1991个9可以分为若干段这种数（每一段中有3个9）．因为1991 ÷3＝663……2，余数为2，说明去掉这些663段后，还剩2个9．而99＋74＝1……25，所以由1991个9组成的多位数999…99除以74所得的余数是25． 例5一串数1、2、4、7、11、16、22、29…这串数的组成规律，第2个数比第1个数多1；第3个数比第2个数多2；第4个数比第3个数多3；依次类

同余的概念与性质

同余的概念与性质 同余：设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 ≡。

小学奥数—同余问题

数论之同余问题 余数问题是数论知识板块中另一个内容丰富，题目难度较大的知识体系，也是各大杯赛小升初考试必考的奥数知识点，所以学好本讲对于学生来说非常重要。 许多孩子都接触过余数的有关问题，并有不少孩子说“遇到余数的问题就基本晕菜了！” 余数问题主要包括了带余除法的定义，三大余数定理（加法余数定理，乘法余数定理，和同余定理），及中国剩余定理和有关弃九法原理的应用。 知识点拨： 一、带余除法的定义及性质： 一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q……r，也就是a＝b×q＋r, 0≤r＜b；我们称上面的除法算式为一个带余除法算式。这里： r=时：我们称a可以被b整除，q称为a除以b的商或完全商 (1)当0 r≠时：我们称a不可以被b整除，q称为a除以b的商或不完全商 (2)当0 一个完美的带余除法讲解模型: 如图，这是一堆书，共有a本，这个a就可以理解为被除数， 现在要求按照b本一捆打包，那么b就是除数的角色，经过打包后 共打包了c捆，那么这个c就是商，最后还剩余d本，这个d就是 余数。 这个图能够让学生清晰的明白带余除法算式中4个量的关系。并且可以看出余数一定要比除数小。 二、三大余数定理： 1.余数的加法定理 a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。 例如：23，16除以5的余数分别是3和1，所以23+16=39除以5的余数等 于4，即两个余数的和3+1. 当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。

例如：23，19除以5的余数分别是3和4，故23+19=42除以5的余数等于3+4=7除以5的余数，即2. 2.余数的乘法定理 a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。 例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1=3。 当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。 例如：23，19除以5的余数分别是3和4，所以23×19除以5的余数等于3×4除以5的余数，即2. 3.同余定理 若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：a≡b ( mod m )，左边的式子叫做同余式。 同余式读作：a同余于b，模m。由同余的性质，我们可以得到一个非常重要的推论： 若两个数a，b除以同一个数m得到的余数相同，则a，b的差一定能被m整除 用式子表示为：如果有a≡b ( mod m )，那么一定有a－b＝mk,k是整数，即m|(a－b) 三、弃九法原理： 在公元前9世纪，有个印度数学家名叫花拉子米，写有一本《花拉子米算术》，他们在计算时通常是在一个铺有沙子的土板上进行，由于害怕以前的计算结果丢失而经常检验加法运算是否正确，他们的检验方式是这样进行的： ++++= 例如：检验算式1234189818922678967178902889923 1234除以9的余数为1 1898除以9的余数为8 18922除以9的余数为4 678967除以9的余数为7 178902除以9的余数为0 这些余数的和除以9的余数为2

第5讲同余的概念和性质

第5讲同余的概念和性质 解题思路：理解并熟记同余的性质，运用同余性质把数化小、化易。 同余定义：若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为： a≡b（modm）. 性质1：若a≡b（mod m），b≡c（mod m），那么a≡c（mod m），（传递性）。 ★性质2：若a≡b（mod m），c≡d（mod m），那么a±c≡b±d（mod m），（可加减性）。 ★性质3：若a≡b（mod m），c≡d（mod m），那么ac≡bd（mod m）（可乘性）。 性质4：若a≡b（mod m），那么a n≡b n（mod m），（其中n为自然数）。 性质5：若ac≡bc（mod m），（c，m）=1，那么a≡b（mod m），（记号（c，m）表示c与m的最大公约数）。 例1 判定288和214对于模37是否同余，74与20呢 例2 求乘积418×814×1616除以13所得的余数。 例3 求14389除以7的余数。

例4 四盏灯如图所示组成舞台彩灯，且每30秒钟灯的颜色改变一次，第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，…，这样一直进行下去.请问开灯1小时四盏灯的颜色如何排列 十位，…上的数码，再设M=0a ＋0a ＋…＋n a ，求证：N ≡M （mod 9） 例6 求自然数1002＋1013＋1024的个位数字。 习题 1.验证对于任意整数a 、b ，式子a ≡b （mod1）成立，并说出它的含义。 2.已知自然数a 、b 、c ，其中c ≥3，a 除以c 余1，b 除以c 余2，则ab 除以c 余多少 年的六月一日是星期二，这一年的十月一日是星期几 4.求＋被7除的余数。