初等数论课程教案(第三章)

格式：ppt
大小：701.00 KB
文档页数：73

下载文档原格式

/ 73

初等数论课程设计

初等数论课程设计一、教学目标本课程旨在通过数论的学习，使学生掌握数论的基本概念、性质和定理，培养学生解决实际问题的能力，提高学生的逻辑思维和数学素养。

具体的教学目标如下：1.知识目标：（1）了解数论的基本概念，如整数、素数、最大公约数等。

（2）掌握数论的基本性质和定理，如素数的分布、费马小定理等。

（3）学会运用数论知识解决实际问题，如密码学、计算机科学中的问题。

2.技能目标：（1）能够运用数论知识进行计算和证明。

（2）培养学生的逻辑思维和分析问题的能力。

（3）提高学生的数学写作和表达能力。

3.情感态度价值观目标：（1）培养学生对数学的兴趣和热情，提高学生的数学素养。

（2）培养学生团队合作和自主学习的能力。

（3）培养学生的创新精神和批判性思维。

二、教学内容本课程的教学内容主要包括数论的基本概念、性质和定理。

具体安排如下：1.第一章：数论基础（1）整数和分数（2）素数和合数（3）最大公约数和最小公倍数2.第二章：素数的分布（1）素数定理（2）素数的计算（3）素数的存在性3.第三章：同余理论（1）同余的基本概念（2）费马小定理（3）欧拉定理4.第四章：数论应用（1）密码学中的应用（2）计算机科学中的应用（3）实际问题中的应用三、教学方法为了提高教学效果，本课程将采用多种教学方法相结合的方式进行教学。

具体方法如下：1.讲授法：通过教师的讲解，使学生掌握数论的基本概念和定理。

2.讨论法：引导学生进行分组讨论，培养学生的团队合作和分析问题的能力。

3.案例分析法：通过分析实际问题，使学生学会将数论知识应用于解决实际问题。

4.实验法：引导学生进行数学实验，培养学生的动手能力和创新精神。

四、教学资源为了支持教学内容和教学方法的实施，本课程将采用以下教学资源：1.教材：选用国内权威的数论教材，为学生提供系统的数论知识。

2.参考书：提供相关的数论参考书，丰富学生的学习资料。

3.多媒体资料：制作多媒体课件，提高课堂教学效果。

《初等数论(闵嗣鹤、严士健)》第三版课件3-1

m a b , 则m m q1 q2 r1 r2 ,因此m r1 r2 , 但 r1 r2 m , 故r1 r2 .
a b mod m , 则r1 r2 ,因此a b m q1 q2 .反之若
4
1
TH2 设a，b，c，d，k是整数，并且 a b (mod m)， c d (mod m)，
1
§3.1 一、问题的提出
同余的概念及其基本性质
1、今天是星期一，再过100天是星期几？
再过1010 天呢？ 2、3145×92653=2910 93995的横线处漏写了一个
数字，你能以最快的办法补出吗？
3、13511，13903，14589被自然数m除所得余数
相同，问m最大值是多少？ 4、你知道 77 的个位数是多少吗？
i 0 i 0
n
n
证(1) 设a b mq1 , c d mq2 ,因此 a c b d m q1 q2
证明 :由x y(mod m )得x i y i (mod m ),
由ai bi (mod m )得ai x i bi y i (mod m ),
若ab c , 则有 ab a b c(mod 9) 应用这种方法可以验算较大整数的乘法。例5. 验算 28997×39495＝1145236415是否正确。
28997 17 8(mod 9)， 39495 3(mod 9)
1145236415 32 5(mod 9)
——各位上的数字之和能被3（9）整除 10 1mod(3) 10i 1mod(3)
a an 10n a1 10 a0 an a1 a0 mod(3)

初等数论课程教案总结.ppt

最大公约数 : 设 a1, a2是两个不全为零的整数 . 我们把 a1和 a2 的公约数中最大的称为 a1 和 a2 的最大公约数 , 记作 ( a1, a2 ) , 一般地 , 设 a1,. . . ,ak 是 k 个不全为零的整数 . 我们把 a1,. . . , ak 的公约数中最大的称为 a1,. . . , ak 的最大公约数 , 记作 ( a1,. . . , ak ) .
P 1 8 定理 1 2 : 设 m 0,我们有
[ ma1,. . . , mak ] = m[a1,. . . , ak ] .
P 2 0 定理 2 ：设 a,b是两个给定的整数 , a 0. 再设 d是一个给定的整数. 那么,一定存在惟一的一对整数 q1 与 r1, 满足 b a q1 r1,d r1 a d. 此外 , a b的充要条件是 a r1.
P 4 4 定理 8 ：设 a1,,ak是不完全为零的整数 . 我们有 ( i ) ( a1,, ak ) = m i n { s a1x1 ak xk : x j Z( 1 j k ) , s 0} , 即 a1,, ak 的最大公约数等于 a1,,ak的所有整系数线性组合组成的集合 S中的最小正整数 . ( i i ) 一定存在一组整数 x1,0,, xk,0使得 ( a1,, ak ) = a1x1,0 ak xk,0.
P 4 8 定理 1 ：设 p 是素数 , p a1a2 . 那么 p a1或 p a2 至少有一个成立 . 一般地 , 若 p a1. . .ak , 则 p a1 ,. . . , p ak 至少一个成立.

优选初等数论第三章课件

(4)若a1 b1(mod m), a2 b2 (mod m)，则 a1 a2 b1 b2 (mod m);
若a b c(mod m),则a c b(mod m)
(4)若a1 b1(mod m), a2 b2 (mod m)，则 a1a2 b1b2 (mod m);
若a b(mod m),则ak bk(mod m)
i p
pq,
即p
C
i p
例3、（1）求所有的正整数n，使得2n 1能被7整除；（2）证明：对于任何正整数n，2n +1不能被7整除。
解：（1）n Z ,都可写成3m k的形式,其中m N, k 0,1, 2. 因为23 1(mod 7)，所以23m 1(mod 7)，即23m 1 0(mod 7), 从而当 n 3m, 7 2n 1；
证：不妨设Sn 1n 2n 3n 4n，容易验证,14 1(mod 5), 24 16 1(mod 5),34 81 1(mod 5), 44 256 1(mod 5),
假定4k r,其中r 0,1, 2,3.由以上知 a4 1(mod 5), a 1, 2,3, 4. 则有 a4k 1(mod 5), 所以an a4kr ar (mod 5)
(6)若a b(mod m),且a a1d,b b1d,(d, m) 1，则 a1 b1(mod m)
(7)若a b(mod m), k 0,则 ak bk(mod mk) 若a b(mod m), d a,b, m, d 0，则
a d
b d
mod
m d
(8)若a b(mod mi ),i 1, 2, , k,则 a b(mod[m1, m2, , mk ])
因此可得Sn 1n 2n 3n 4n 1r 2r 3r 4r (mod 5). 因而当r 0,1, 2,3时，依次有 Sn 4 4(mod 5)， Sn 10 0(mod 5)，Sn 30 0(mod 5)，Sn 100 0(mod 5)，故当且仅当n不能被4整除时，1n 2n 3n 4n能被5整除.

初等数论第三章课件

, n 1)时，每一项3i xi 各取3个值， 3x1 x0共通过3n 1 个数；
② 在这3n 1 个数中，若有 3n 1 xn 1 3n xn x0 =3n xn 3n 1 xn 1 3x1 3x1 x0 3n ( xn xn ) 3n 1 ( xn 1 xn 1 ) 则x0 x0 x0 x0 3 x0 x0 x1 ) 3( x1
同余的一个应用——检查因数的一些方法
A、一整数能被3（9）整除的充要条件是它的十进位数码的和能被3（9）整除。
证：a Z , 将a写成十进位数的形式： a an10 an 110
n
i n n
n 1

a0 , 0 ai 10.
i n
因10 1(mod 3), 故10 1(mod 3), ai 10 ai (mod 3), 从而 ai 10i ai (mod 3),即a ai (mod 3).
n
n 1
3 x1 x
也是模3 =2H+1的绝对最小完全剩余系。（再由模2H+1的绝对最小完全剩余系具有唯一性得到结论）
① 3n xn 3n 1 xn 1 xi 1, 0,1(i 0,1, 故3n xn 3n 1 xn 1
3x1 x0共有n 1项，当
i ! p( p 1)
( p i 1) Z i! ( p i 1)
当i 1, 2, 故C ip pq,
, p 1时, (i !, p) 1 即p C ip
i ! ( p 1)
( p i 1)，
例3、（ 1）求所有的正整数n，使得2n 1能被7整除；（2）证明：对于任何正整数n，2n +1不能被7整除。

(完整版)初等数论教案

初等数论教案一、数论发展史数论是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布以及数论函数等内容，统称初等数论（Elementary Number Theory ）。

初等数论的大部分内容早在古希腊欧几里德的《几何原本》中就已出现。

欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，即所谓欧几里得算法。

我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”正是我国古代《孙子算经》中的下卷第26题，我国称之为“孙子定理”。

近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。

1801年，高斯的《算术探究》是数论的划时代杰作。

“数学是科学之王，数论是数学之王”。

-----高斯由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等新分支。

而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时间促进着数论的发展。

二几个著名数论难题初等数论是研究整数性质的一门学科，历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。

其中，非常著名的问题有：哥德巴赫猜想；费尔马大定理；孪生素数问题；完全数问题等。

1、哥德巴赫猜想：1742年,由德国中学教师哥德巴赫在教学中首先发现的。

1742年6月7日，哥德巴赫写信给当时的大数学家欧拉,正式提出了以下的猜想：一个大于6的偶数可以表示为不同的两个质数之和。

陈景润在1966年证明了“哥德巴赫猜想”的“一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和”〔所谓的1+2〕，是筛法的光辉顶点，至今仍是“哥德巴赫猜想”的最好结果。

2、费尔马大定理：费马是十七世纪最卓越的数学家之一，他在数学许多领域中都有极大的贡献，因为他的本行是专业的律师，世人冠以“业余王子”之美称。

初等数论教程3

• 比如时间的表示：我们说15:00与说下午3:00是一样的，因为15除以12与3除以12余数也相同，都为3。
• 即：120=7×17+1，365=7×52+1；15=12×1+3， 3=12×0+3
记为：120 365mod7 ；15 3mod12 。
并称为 120 与 365 对模 7 同余；15 与 3 对模 12 同余。
若 r1 r2，则称 a和 b对于模 m不同余，记作 a b(mo d m).
例3.1（P.121）
练习：（1）142与43对模11是否同余？（2）13与3对模5是否同余？（3）7与7对模7是否同余？（4）2与-2对模3是否同余？
例3.2 求证（1）如果a除以m的余数为r （ 0 r m ），则 a r(modm) ；（2）如果 a r(modm) ，0 r m ，则a除以m的余数为r.
b不是a对模m的剩余,
记作
a b (mod m);

关系式(1)称为模m的同余式,或简称同余式.
注：
由于m a b等价于-m a b,所以同余式(1) 等价于 a b (mod ( - m));
因此,以后总假设m 1.在同余式(1)中, 若0 b m ,则称b 是a 对模m的最小非负剩余; 若1 b m ,称b是a 对模m的最小正剩余; 若 - m / 2 b m / 2 (或 m / 2 b m / 2) ,称 b 是 a 对模 m 的绝对最小剩余.
• 下面的四个叙述是等价的： • (ⅰ) a b (mod m)； • (ⅱ) m|(a-b); • (ⅲ) 存在整数q，使得a = b qm； • (iv) 存在整数q1，q2，使得a=mq1 r，

《初等数论》课程教学标准

《初等数论》课程教学标准第一部分：课程性质、课程目标与教学要求《初等数论》是数学与应用数学本科专业的一门专业选修课，该课程是综合应用近现代数学的工具，来处理与整数相关的问题。

在计算方法、代数编码、组合论、信息安全与密码学等方面有着广泛的应用。

同时由于数论问题的丰富性、多样性及解题所具有的高度技巧，对培养灵活创新的思维品质，逻辑思维、发散思维能力，系统地掌握各种数学思维方法都是不可缺少的。

本课程对培养中学数学教师和从事数学研究都具有特殊重要的作用。

通过对《初等数论》的学习，使学生了解数论中的一些著名问题，比如哥德巴赫猜想、费尔马大定理等；了解数论在计算方法、代数编码、组合论、信息安全与密码学等方面的广泛应用；熟练掌握初等数论的基本内容、基本思想与基本方法；加深对整数的理解，更深入地理解某些相邻学科；培养学生的数学思维，从而提高分析问题解、决问题的能力。

第二部分：关于教材与学习参考书的建议本课程拟采用高等教育出版社2003年7月第三版、由闵嗣鹤,严士健主编的《初等数论》一书，作为本课程的主教材。

为了更好地理解和学习课程内容，建议学习者可以进一步阅读以下几本重要的参考书：1、《初等数论》潘承洞，潘承彪，北京大学出版社1992。

2、《初等数论》周显，华东师大出版社1984。

3、《初等数论》冯克勤，余红兵，合肥、中国科学技术出版社4、《数论基础》王杰官，福建科学技术出版社。

第三部分：课程教学内容纲要《初等数论》主要内容有：整数整除性理论、不定方程、同余、同余式、平方剩余与二次同余式等内容。

其中整除性理论、同余式理论是初等数论课程的基本内容，解不定方程、解同余式是这些理论的最基本的应用。

其各章各章的重点与难点第一章整数的整除性理论重点：整除的基本性整数质及其应用，最大公约数与最小公倍数、素数、算术基本定理。

难点：有关素数问题的探讨及整除性理论在中学数学竞赛问题中的应用。

第二章不定方程重点：二元一次不定方程、多元一次不定方程的有整数解的条件、解法、解结构，了解勾股数及费尔马问题。

《初等数论》课程教学大纲

《初等数论》课程教学大纲一、教师信息二、课程基本信息课程名称（中文）：初等数论课程名称（英文）：Elementary Number Theory课程性质：□公共必修课√□专业必修课□限选课□任选课□实践性环节课程性质: √□学术知识类□方法技能类□研究探索类□实践体验类课程代码：4230070周学时： 2 总学时：32 学分: 2先修课程：高中数学授课对象：小学教育（理科）三、课程简介本课程是《小学数学课程与教学》的前修课程，是小学教育专业的本科生（理科）必不可少的基础知识之一，为以后指导小学数学教育提供有用的理论依据，并能直接指导小学数学课外活动。

首先，采用不太多的数学知识，由浅入深地介绍初等数论的基本原理和解题方法与技巧，如整数的整除理论及其在小学数学教学中的指导作用，素数的部分性质，及其同余的基本原理与同余式（组）的解法等。

其次，联系小学数学的教学内容和小学数学竞赛的辅导内容，突出讲解整除性理论在小学数学中的地位，和介绍数的K进位制的意义和计算，对整数和分数的四则运算的指导作用，以及四则运算中的运算技巧等。

再次，整除性理论中讲解奇偶性分析在解题中的作用，介绍不定方程中的著名问题“百鸡问题”、“费马问题”，同余式内容中，介绍我国古代数学书中提出的问题“韩信点兵”的“中国剩余定理”（孙子定理）等，以体现初等数论的应用性，提高学生对数学和小学数学教学的兴趣。

四、课程目标1.了解经常出现在生活中的自然数和整数的一些性质，了解初等数论与算数的关系；2.掌握整数的整除性、不定方程和同余式等基本知识；通过较系统的学习，掌握这门学科的基本数学思想和方法。

3.了解数论在我国的古代就已有极其光辉的成就，如孙子定理等。

五、课程内容与进度安排（一）课程内容第一章整数的可除性1.课时数（10）2．讲授内容主要知识点：（1）整除的概念、带余除法；（2）整除性定理；（3）奇数和偶数；（4）最大公约数和最小公倍数；（5）质数和合数（算术基本定理）重点：整除的概念、带余除法、最大公约数和辗转相除法、最小公倍数的性质、约数和算术基本定理。

大学初等数论教案

1. 知识目标：（1）使学生掌握初等数论的基本概念、性质和定理；（2）使学生了解初等数论的研究方法和应用领域；（3）培养学生逻辑推理、抽象思维和数学建模能力。

2. 能力目标：（1）提高学生运用数学知识解决实际问题的能力；（2）培养学生独立思考、团队合作和创新能力。

3. 情感目标：（1）激发学生对数学的兴趣和热爱；（2）培养学生的严谨求实、勇于探索的科学精神。

二、教学内容1. 整数的基本性质；2. 同余及同余定理；3. 素数与哥德巴赫猜想；4. 最大公约数与最小公倍数；5. 完全数与亲和数；6. 数论的应用。

三、教学方法1. 讲授法：系统讲解数论的基本概念、性质和定理；2. 讨论法：引导学生积极参与课堂讨论，培养合作精神；3. 案例分析法：通过实际案例，提高学生运用数学知识解决实际问题的能力；4. 练习法：布置课后习题，巩固所学知识。

1. 导入新课（1）介绍数论的研究背景和意义；（2）提出本节课的学习目标。

2. 讲解整数的基本性质（1）讲解整数的定义、性质和运算；（2）举例说明整数的基本性质。

3. 讲解同余及同余定理（1）讲解同余的定义、性质和运算；（2）讲解同余定理，并举例说明。

4. 讲解素数与哥德巴赫猜想（1）讲解素数的定义、性质和分布；（2）介绍哥德巴赫猜想及其相关研究。

5. 讲解最大公约数与最小公倍数（1）讲解最大公约数和最小公倍数的定义、性质和计算方法；（2）举例说明最大公约数和最小公倍数的应用。

6. 讲解完全数与亲和数（1）讲解完全数和亲和数的定义、性质和寻找方法；（2）举例说明完全数和亲和数的应用。

7. 讲解数论的应用（1）介绍数论在密码学、计算机科学等领域的应用；（2）举例说明数论在实际问题中的应用。

8. 课堂小结（1）回顾本节课所学内容；（2）强调数论的重要性和应用价值。

9. 作业布置（1）布置课后习题，巩固所学知识；（2）鼓励学生查阅相关资料，拓展知识面。

五、教学评价1. 课堂表现：观察学生的课堂参与度、回答问题的准确性和完整性；2. 课后作业：检查学生的作业完成情况，了解学生对知识的掌握程度；3. 期中期末考试：综合评价学生的学习成果。

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

例求 6125 m o d 4 1 和 5111 m o d 2 3 . 解首先找到一个整数 d , 满足 6 d 1 (mod 41). 由 6 2 5 (mod 41); 6 4 25 (mod 41); 6 5 27 (mod 41); 610 9 (mod 41); 6 20 1 (mod 41); 6 40 1 (mod 41). 可取 d 40,从而 6 4035 27 (mod 41). 由 5 2 2 (mod 23); 5 4 4 (mod 23); 58 7 (mod 23); 516 3 (mod 23); 5 20 12 (mod 23); 5 22 1 (mod 23); 取 d 22,所以 5 2251 5 (mod 23).
定理 1 a 同余于b 模m的充要条件是 a 和b 被 m除后所得的最小非负余数相等,即若 a q1m r1 , 0 r1 m; b q2 m r2 , 0 r2 m; 则 r1 r2 . 证我们有 a b (q1 q2 )m (r1 r2 ).因此 , m a b 的充要条件是 m r1 r2 ,由此及 0 r1 r2 m 即得 r1 r2 . 定理1表明可以用最小非负余数相等来定义同余.
例求最小的 m n, 使得 1 0 4 16 8 m - 1 6 8 n . 解求 1 0 4 16 8 m - 1 6 8 n即要求如下同余式： 168n (168mn 1) (23 3 7) n (168mn 1) 0(mod 2 3 13) 等价于 (23 3 7) n (168mn 1) 0(mod 23 ) 3 n mn (2 3 7) (168 1) 0(mod 13)
当满足式 ( 5 ) 时 , 称多项式 f ( x)等价于多项式 g ( x) 模 m, 式 ( 5 ) 称为模 m 的恒等同余式 .
性质 V 设 d 1, d m. 那么 , 若同余式 ( 1 ) 成立 , 则 a b (mod d ). 证由 d m , m a b d a b即得 . 性质 V I 设 d 0. 那么同余式 ( 1 ) 等价于 da db (mod d m). 证由 d m da db m a b 推出 .
性质 II 同余可以相加减 , 即有 a b (mo d m), c d (mo d m),则 a c b d (mo d m). 证由 m a b , m c d m ( a b ) (c d ) ( a c ) (b d ). 性质 III 同余可以相乘 , 即有 a b (mo d m), c d (mo d m),则 a c b d (mo d m). 证由 a b k1m, c d k2 m 推出 a c b d (b k2 d k1 k1k2m) m
由于 m a b等价于 - m a b ,所以同余式 ( 1 ) 等价于 a b (mod ( - m)); 因此 , 以后总假设 m 1. 在同余式 ( 1 ) 中 , 若 0 b m ,则称 b 是 a 对模 m 的最小非负剩余 ; 若 1 b m ,称 b 是 a 对模 m 的最小正剩余/ 2 b m / 2) , 称 b 是 a 对模 m 的绝对最小剩余.
性质 V I I 同余式 ca cb (mod m) (7) 等价于 a b (mod m / (c, m)). 特别地 , 当 (c, m) 1时 , 同余式 ( 7 ) 等价于 a b (mod m), 即同余式两边可约去 c. 证同余式 ( 7 ) 即 m c (a b), 这等价于 m c (a b). ( c, m ) ( c, m ) 由第一章 § 4 定理 6 及 ( m / (c, m), c / (c, m) ) = 1 知 , 这等价于 m (a b). ( c, m)
性质I 同余是一种等价关系, 即有自反性 a a (mod m),
对称性 a b (mod m) b a (mod m), 传递性 a b (mod m), b c (mod m) a c (mod m). 证由 m a a 0, m a b m b a ,以及 m a b, m b c m (a b) (b c ) a c
例 2 求 3 406写成十进位数时的最后两位数 . 解只要求出 b 满足 3 406 b (mod 100),0 b 99. 注意到 1 0 0 = 4 2 5 , ( 4 , 2 5 ) = 1 , 显然有 , 3 2 1 (mod 4), 3 4 1 (mod 5). 注意到 4 是最小的方次 , 由第一章 § 4 例 5 知 , 使 3 d 1 (mod 25) 成立的 d , 必有 4 d .因此计算 3 4 81 6 (mod 25), 38 36 11 (mod 25), 312 66 9 (mod 25), 316 54 4 (mod 25), 3 20 24 1 (mod 25),由此及 3 20 1 (mod 4), 从性质 IX 推出 3 20 1 (mod 100), 3 400 1 (mod 100).因此 3 406 3 400 3 6 3 6 29 (mod 100).所以个位数是 9 , 十位数是 2 .
定义 2 设 f ( x) an x n ... a0 , g ( x) bn x n ... b0 是两个整系数多项式 . 当满足条件 ( 4 )时 , 称多项式 f ( x)同余于多项式 g ( x)模 m, 记作 f ( x) g ( x) (mod m); (6)
性质 IV 设 f ( x) an x ... a0 , g ( x) bn x ... b0
n n
是两个整系数多项式,满足 a j b j (mod m),0 j n. 那么 , 若 a b (mod m),则 f (a) g (b) (mod m). 特别的,对所有整数 x 有 f ( x) g ( x) (mod m) (5) (4)
由于 ( 2 3 , ( 3 7 ) n (168mn 1) ) = 1 , ( ( 23 3 7) n ,13) = 1 , 满足性质 VII 中消去律的条件.所以等价于： 23n 0(mod 23 ) k 168 1 0(mod 13)
例设n为整数,试求出它能为9整除的判别方法. 解 n a010k a110k 1 ak 110 ak 因为 10 1 (mod 9),1 i k , 所以由性质得，
i
n a0 a1 ak 1 ak (mod 9). 故只要 0 a0 a1 ak 1 ak (mod 9),则 n 可被9整除.
定理 1 (i) r mod m { r km : k Z }; (ii) r mod m s mod m 的充要条件是 r s mod m; (iii) 对任意的 r , s, 要么 r mod m s mod m, 要么 r mod m 与 s mod m 的交为空集.
容易验证第一个方程有解的最小的n为1;第二个方程有解的最小的 n 为 2 , 所以 , 使 1 0 4 16 8 m - 1 6 8 n成立的最小的 m n (1 2) 1 4 .
§2 同余类与剩余类
定义 1 同余类 ( 剩余类）对给定的模 m,整数的同余关系是一个等价关系,因此全体整数可按对模m 是否同余,分为若干个两两不相交的集合,使得在同一个集合中任意两个数对模m一定同余,而属于不同集合中的两个数对模m一定不同余.每一个这样的集合称为是模 m 的同余类 , 或模 m 的剩余类 . 我们以 r mod m 表 r 所属的模m的同余类.
性质 Ⅷ 若 m 1,(a, m) 1,则存在 c 使得 ca 1 (mod m),我们把 c 称为是 a 对模 m 的逆，记作 a 1 b (mod m)或 a 1. 证由第一章 § 4 定理 8 ( k 2 ) 知 , 存在 x0 , y0 , 使得 ax0 my0 1. 取 c x0 既满足要求 . 由此提供一种求 a 1 (mod m)有效的方法 , 这是Euclid算法的又一重要应用.
性质 I X 同余式组 a b (mod m j ), j 1,2,..., k , 同时成立的充要条件是 a b (mod [ m1 ,..., mk ]). 证由第一章 § 4 定理 1 知 , m j a b ( j 1,, k ) 同时成立的充要条件是 [ m1 ,..., mk ] a b .
例求 p 11 所有元的逆元 . 解由 1 ( - 1 0 ) + 1 1 = 1 得 1 1 ( 10) 1 (mod 11) 由 2 ( - 5 ) + 1 1 = 1 得 2 1 ( 5) 6 (mod 11); 同样计算得： a a1 1 2 3 4 5 6 7 8 9 10 1 6 4 3 9 2 8 7 5 10