初等数论期末复习分析课件.ppt

1、2022年年5月月31日日10时时02分分1、同余的概念、同余的概念:定义定义2. 1 若若a 和和b 除以除以m 所得余数不同，则称所得余数不同，则称a，b 对模对模m 不同余，记作不同余，记作 a b (mod m). 设设m为正整数，称为模。若用为正整数，称为模。若用m去除两去除两个整数个整数 a 和和 b 所得的余数相同，则称所得的余数相同，则称a 和和b 对模对模 m 同余同余, 记作记作 a b (mod m). （1） 读作读作a 同余于同余于b 模模m。一、同余的概念及基本性质一、同余的概念及基本性质2022年年5月月31日日10时时02分分2、同余的性质：、同余的性质：(1)

2、 反身性：反身性： 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).(4) 若若a b (mod m)，c d (mod m) ， 则则 a + c b + d (mod m) , ac bd (mod m).同余式可以相加减。同余式可以相加减。2022年年5月月31日日10时时02分分我喜欢数学我喜欢数学性质性质(5) 若若a b (mod m)，c d (mod m) ， 则则 ac bd (mod m) .同余式可

3、以相乘。同余式可以相乘。推论推论若若a b (mod m)， 则则 a k b k (mod m), k 为任意整数为任意整数.同余式的数乘。同余式的数乘。2022年年5月月31日日10时时02分分性质性质(6)性质性质(7) 若若a =a1d, b =b1d, (m, d) =1, a b (mod m)，则，则 a1 b1 (mod m) .性质性质(8) da，bm(mod).abmddd若若a b (mod m)，k 为正整数为正整数 ， 则则 ka kb (mod km) .2022年年5月月31日日10时时02分分性质性质(9)若若 a b (mod m1), a b (mod m

4、2), m= m1, m2 , 则则 a b (mod m) . 性质性质(10) 设设d 1， d | m，若，若a b (mod m) ， 则则 a b (mod d ) .若若a b (mod m)，则，则 (a，m) = (b，m).性质性质(11)2022年年5月月31日日10时时02分分正整数四则运算正整数四则运算(含乘方含乘方) 的快速验算方法的快速验算方法例例7 用用弃九法弃九法验算验算 2894734578 =1001865676 是否正确是否正确. 弃九法只是运算结果正确的必要条件，而非充弃九法只是运算结果正确的必要条件，而非充分条件分条件 ! 因此只能因此只能判误判误.2

5、89473 (mod 9), 345780 (mod 9)应有应有2894734578 0 (mod 9), 而而1001865676 0 (mod 9), 所以计算必有错误所以计算必有错误.解解若通过计算，若通过计算，a、b的和与积分别是的和与积分别是s与与p. 而而r1、r2、r3、r4 分别是分别是a、b、s、p被被 9 除所得的余数除所得的余数, 由由同余同余的加减乘性质的加减乘性质可知，可知，如果如果r1 +r2与与r3、 r1 r2与与r4关关于模于模 9 不同余，那么计算一定错了不同余，那么计算一定错了.2022年年5月月31日日10时时02分分例例1 求求7406写成十进制数时

6、的个位数。写成十进制数时的个位数。a 0 (mod m).72 49 1(mod 10), 或或 74 1(mod 10), 7406 7404 729 (mod 10).(72 )203 1 9 (mod 10),2022年年5月月31日日10时时02分分二、剩余类与剩余系二、剩余类与剩余系定理定理2.2.1 设设m为正整数，则全部整数可分成为正整数，则全部整数可分成m个个集合集合,记作记作0，1，m1，其中，其中r (0 r m1)是由一切形如是由一切形如 mq + r (qZ) 的整数所组的整数所组成的，并且具有下列性质：成的，并且具有下列性质：(1)每一整数必包含在而且仅在上述的一个集

7、合中每一整数必包含在而且仅在上述的一个集合中.(2)两个整数同在一个集合中的充分必要条件为这两个整数同在一个集合中的充分必要条件为这两个整数对模两个整数对模 m 同余。同余。2022年年5月月31日日10时时02分分定义定义2. 2 设设m为正整数，则全部整数分成的为正整数，则全部整数分成的 m个个集合集合0，1，m1称为称为模模m的剩余类的剩余类,一一个个剩余类剩余类中任一数叫做它的同类的数的剩余。中任一数叫做它的同类的数的剩余。2022年年5月月31日日10时时02分分定理定理2.2.2设设m为正整数，则为正整数，则 （1）在任意取定的）在任意取定的 m + 1 个整数中，必个整数中，必有

8、两个数对模有两个数对模 m 同余。同余。 （2）存在）存在 m 个数两两对模个数两两对模m不同余。不同余。完全剩余系完全剩余系定义定义2. 3 设设 m 为正整数，则从模为正整数，则从模 m 的每个的每个剩余类中各取一个数所作成的集合，称为剩余类中各取一个数所作成的集合，称为模模 m 的一个的一个完全剩余系完全剩余系.2022年年5月月31日日10时时02分分定理定理2.2.4 若若 a1, a2，, am 是模是模m的完全剩余系，的完全剩余系，且且(a, m) =1, b 为任意整数，则为任意整数，则 aa1 +b, aa2 +b, , aam +b 也是模也是模 m 的一个完全剩余系。的一

9、个完全剩余系。定理定理2.2.3设设m 为正整数，整数集合为正整数，整数集合 a1, a2 , , am是模是模 m 的完全剩余系的充分必的完全剩余系的充分必要条件是：要条件是：ai aj (mod m) ( i j ). 0,1,1,mm注：最常见的完全剩余系是它们称非负最小完全为模 的剩余系.下面例1给出模m的另外完全剩余系绝对最小完全剩余系.,1, 1,0,1,12221,1, 1,0,1,222mmmmmmm例2 当 是偶绝对最数时及小完是模m的全剩余系-1-1-1,1, 1,0,1,222.mmmmm当绝对最小完是奇全时是模 的剩余系数2022年年5月月31日日10时时02分分例例3

10、 验证：验证：11, 4, 18, 20, 32 是模是模 5 的一的一个完全剩余系。个完全剩余系。证：只要证两两不同余即可证：只要证两两不同余即可, 也就是它们各也就是它们各属于不同的剩余类属于不同的剩余类. 从而只要证明它们各从而只要证明它们各与与最小非负完全剩余系最小非负完全剩余系中的某一个数同余中的某一个数同余即可即可.11与与4, 4与与1, 18与与3, 20与与0, 32与与2分分别对模别对模5同余，所以结论成立。同余，所以结论成立。2022年年5月月31日日10时时02分分定义定义 2.42.411( )1.mmm ( )1.mm ? (m)? (m)2022年年5月月31日日

11、10时时02分分定义定义 2.52.5定理定理2.2.6设设 m 是正整数，则模是正整数，则模m的一个剩余类是的一个剩余类是与模与模 m互质的剩余类的充分必要条件为：这个模互质的剩余类的充分必要条件为：这个模m的剩余类中有一数与的剩余类中有一数与m互质。互质。2022年年5月月31日日10时时02分分简化剩余系的充要条件简化剩余系的充要条件定理2.2 7 整数集合为模m的简化剩余系的充要条件是充要条件是： ( i ) (ai, m) =1 ( 1i ? (m) ); ( ii ) 各数关于模m两两不同余12() ,ma aa2022年年5月月31日日10时时02分分定理 2.2.10若若 m

12、的标准分解式是的标准分解式是1212,kkmp pp则则欧拉函数的计算公式欧拉函数的计算公式推论推论 若若 则则1212()() ().m mmm12(,)1,m m定理定理 2.2.8 若( a，m ) = 1 , x 通过模 m 的简化剩余系，则 ax 也通过模 m 的简化剩余系。 即即x1, x2, xk是模是模m的一个简化剩余系，则的一个简化剩余系，则ax1, ax2, , axk也是模也是模m的简化剩余系。这里的简化剩余系。这里k = ? (m)。2022年年5月月31日日10时时02分分欧拉函数欧拉函数? (m) 的计算的计算1212,kkmp pp将代入定理中的公式，就有1111

13、( )( )1iiikkiiiiiimppmpp或特别地，对于质数 p，有 11;ppppp例例 4计算计算? (588000) 解：因解：因 58800025 3 53 7，故由公式可得，故由公式可得? (588000) (25 24) (31) (53 52) (72 7)=19200.2022年年5月月31日日10时时02分分 四欧拉定理四欧拉定理 1(mod).mam定理 2.3.1 ( 欧拉定理) 若为大于1的整数， a为整数且( a ，m) = 1, 则应用实例例5 求112001除以60的余数.解:又(11, 60)=1,由欧拉定理得1116 1(mod 60),故故111612

14、51 (mod 60), 112001 11 (mod 60). 16) 15)(13)(22()60(, 53260221010例7：如果今天是星期二，问从今天起再过11天是星期几？76,7 =1=111 mod7),（ ）解： （11 ） ，（7）6， 11（1010(06),10610(mod 6)rrqrrr先 求使，即 求 ， 使10105510( 2)4( 2)324(mod6), 1010106444221011111141624(mod7),.q故再过11天是星期六 定义定义 3. 1例如同余方程x3 + 2x120 (mod5)定义定义3.2 如果整数如果整数 a 满足满足

15、f (a)0 (mod m) , 那么我们那么我们把把 x a ( mod m）叫做同余方程）叫做同余方程 (1)的一个解的一个解.解同余方程或解同余式即，逐一将 0, 1, ，m1 代入 (1) 中进行验算就可以求得同余方程 (1)的解 上述定义说明, 同余方程 (1)的一个解是 m 的一个剩余类 m 的剩余类只有m个，因此,同余方程 (1)的解的个数最多为 m 我们只需要在模 m 的一组完全剩余系中来确定同余方程 (1)的解例例 1 用直接验算法解同余方程：(1) 11x5 (mod6) ； (2) x3 + 2x120 (mod7) 0, 1, , 5逐一代入(1) 得解 x1 (mod

16、6) 0, 1, , 6逐一代入(2) 求解定义定义: 如果 a , b 都是整数， m 是一个正整数，那么当 a 0 ( mod m）时，我们把 ax b ( mod m ) 叫做模模m的一次同余方程的一次同余方程（或同余式同余式） .定理定理 3.1.1 若设m为正整数, a , b为整数, (a，m)=1，则一次同余方程ax b ( mod m )恰有一个解 .一、欧拉定理法解一次同余方程一、欧拉定理法解一次同余方程定理定理 3.1.2 若 m 为正整数, a , b为整数, (a，m)=1，则一次同余方程ax b ( mod m )的唯一解为 1mod.mxbam一次同余方程有解的判定

17、一次同余方程有解的判定定理定理3.1.3 设设m为正整数，为正整数， a, b是整数，是整数， (a, m)=d，则同，则同余方程余方程 axb (mod m) 有解的充分必要条件为有解的充分必要条件为 d | b.设设m为正整数为正整数, a为整数为整数, (a, m)=d，d | b，则同余方程则同余方程 ax b (mod m) 恰有恰有 d 个解个解一次同余方程有解的解法一次同余方程有解的解法根据同余性质，施行适当的变形变形求解ab(modm):变形(1)：加上或减去模的倍数，推广的加减加减变形， 即 ab+mk (mod m);变形(2)：移项移项变形， 由 ab+c(mod m)

18、可得 acb(mod m);变形(3)：约去同余式两端的公约数，约简约简变形， 由acbc(mod m)，(c, m)d，可得 ab(mod ); 特例：(c, m)1, 由acbc(mod m) 得 ab(mod m)变形(4)：同余式两端同时乘以与模m互质的因数c，即“倍乘倍乘变形”：acbc(mod m)dm（系数消去法）例例 求解同余方程：9x 6 (mod 15)原同余方程的3个解为:解: (9, 15)=3，且3 | 6，可判断方程恰有3个解。 先求解3x2 (mod 5), 3x2+10 (mod 5), x4 (mod 5), x 4 (mod 15), x 9 (mod 15

19、),x 14 (mod 15)或解: 3x3 (mod 5), x1 4 (mod 5), 3组合数法组合数法定理定理 3. 1. 5 若p为质数,且0 a p, 则11 (2)11mod!apppaxbpa 为同余方程ax b (mod p) 的唯一解.1 (2)11!appppaCap例例3 解下列同余方程：7x8(mod 11);解解: 由由11是质数是质数, 且且711, 因而因而 由公式得由公式得 7 110 9 8 7 6 5187!8 309 mod11 .x 本节讨论本节讨论因因 ax+b0 或 axb (mod m) 可以可以通过求解转化为通过求解转化为xc (mod m)

20、, 故我们只讨论故我们只讨论1122mod,mod,mod.kkx c mx c mx c m其中其中求解问题。求解问题。1212,kkm mmc cc为正整数， ， , 为整数的这里这里Mi是同余式是同余式 MiMi 1 (mod mi ) 的解的解, i = 1 ,2 , , n.x M1 M1 b1 + M2 M2 b2 + + MnMnbn (mod m) (2) 恰有一整数解恰有一整数解:1122mod,mod,(1)mod.nnx b mx b mx b m若若n2 , m1 , m2 , , mn 是两两互质的是两两互质的n个正整数，令个正整数，令 m= m1 m2 mn = m

21、1 M1 = m2 M2 = mnMn ，则同余方程组，则同余方程组例 韩信点兵韩信点兵 有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数.解设 x 是所求兵数，则依题意，得1mod5 ,5mod 6 ,4mod 7 ,10mod11 .x x x x 此同余方程组模两两互质，显然有解，且可运用孙子定理求解，过程也比较简捷 。它们两两互素，它们两两互素，b1 =1, b2 =5, b3 =4, b4 =10. 因因此有此有 M = 56711= 2310, M1 = M /m1 = 462, M2 = M /m2 = 385,

22、 M3 = M /m3 = 330, M4 = M /m4 = 210. 这里这里 m1=5 , m2=6, m3=7, m1=11,1mod5 ,5mod 6 ,4mod 7 ,10mod11 .x x x x 解下列同余式解下列同余式得得即即 x = 2111+2310 t ( t = 0, 1, 2, ). 不定方程不定方程是指未知数个数多于方程的个是指未知数个数多于方程的个数，且未知数受到某种条件限制（例如要求数，且未知数受到某种条件限制（例如要求整数解，非负整数解等）的方程。整数解，非负整数解等）的方程。整系数方程 ax + byc 叫做二元一次不定方程，这里a，b，c都是整数，且a

23、b0二元一次不定方程二元一次不定方程 定理4.1.1 二元一次不定方程二元一次不定方程 ax + byc 有解的有解的充分必要条件是充分必要条件是d | c , 这里这里d=(a，b) 定理定理3.1.3 设设m为正整数，为正整数， a, b是整数，是整数， 同余同余方程方程 axb (mod m) 有解的充分必要条件为有解的充分必要条件为 d | b，这里，这里 d = (a, m) . 二元一次二元一次不定方程有解的判定不定方程有解的判定例 判断下列方程有无整数解(1) 12x11y7； (2) 2x+6y8=0；解解(1) 因为(12，11)1，所以原方程有整数解；(2) 由原方程得2x

24、+6y8，由于(2,6)2，2 | 8,所以原方程有整数解；例1 求不定方程 22x+30y=14的一个解11x 7 (mod 15) ， 所以，原方程的一个解是所以，原方程的一个解是 x 2，y 1 解：方法一解：方法一 先解等价的同余方程先解等价的同余方程 (22, 30)=2, 2 | 14, 不定方程有解不定方程有解, 化为化为 11x+15y = 7 后与原方程同解后与原方程同解, 先解等价的同余先解等价的同余方程：方程：将将 x 2 代入代入 11x+15y = 7 ，得，得 y 1，11x 7+15 (mod 15) ， x 2 (mod 15).二元一次二元一次不定方程特解的求

25、法不定方程特解的求法方法一方法一 转化为等价的同余方程转化为等价的同余方程方法二 辗转相除法定理定理4.1.1的充分性证明是构造性证明，给出了求的充分性证明是构造性证明，给出了求方程方程 ax + byc 的一个特解的方法：辗转相除的一个特解的方法：辗转相除法法.若方程有解，则可化为若方程有解，则可化为 ax + by c, (a, b) = 1，必存在整数，必存在整数M，N，使，使 aM + bN 1 ( ）这里的这里的M、N经辗转相除法求出经辗转相除法求出;然后在然后在()式两边同时乘以式两边同时乘以c，得，得 acM + bcN c. 因此不定方程因此不定方程ax + byc的一个整数解

26、就是的一个整数解就是x0cM， y0cN例 解不定方程 22x+30y=14.15=1114, 11=42+3, 4=31+1. 回代：1 = 431= 4(1142)1 =4311=(15111) 311 = 15 3+11(4)，得原方程的一个解： x04728，y0 3721 7 = 11(47) +15 (37).解解: (22, 30)=2, 2 | 14, 不定方程有解, 化为 11x+15y=7, 先解11x+15y=1,辗转相除:方法三 整数分离法 解解 因为(21，57)3，3639，所以原不定方程有整数解在方程两边同时除以3，得7x+19y213. 用辗转相除法求方程(1)

27、的一个整数解的方法不够简便；对于某些二元一次不定方程来说，运用整数分离法求解比较简捷 例例 3 判断不定方程21x+57y639是否有整数解，如果有，请求出它的一个整数解注意到x为整数, 通过观察与估算知 y = 2 时上面的分式为1, x有整数解, 由此得 213 1935302.77yyxy35 2302 225,27xy 为方程的解. 若不能观察到以上结果,可设3 5,573.7yuyu得用较小的系数用较小的系数7去除上式去除上式, 于是有：于是有：继续用上面的方法, 用较小的系数5去除上式, 得3732.55uuyu 可观察到u=1时y有整数解.从而仍然能得出上述的一组解.不定方程的通

28、解不定方程的通解定理定理4.1.2 如果(a, b)=1, 且x x0，y y0是不定方程ax + byc（1）的一个解，那么它的一切解都可表示为0000(2)xxbtxxbtyyatyyat或这里 t 为任意整数。通解公式的特点：0000(2)xxbtxxbtyyatyyat或l公式(2)称为二元一次不定方程(1)的通解公式.其特点是:l (1) 公式中 x，y 的表达式的第一项 x0 ，y0 是方程 (1) 的一个解 (称为特解)；l (2) 公式中 x，y 的表达式的第二项为任意整数 t 乘以不定方程 (1) 的系数或系数的相反数且只要符号保持相反就可以定理4.1.2告诉我们什么?(t为

29、任意整数).0000(2)xxbtxxbtyyatyyat或对于二元一次不定方程(1)，只须用适当方法(观察法，同余法，辗转相除法或整数分离法) 找到它的一组整数解x= x0，y=y0,那么就可以找到方程(1)的一切一切整数解(通解)不定方程的非负整数解不定方程的非负整数解(或正整数解或正整数解)的求法的求法l 实际应用中常常求不定方程的非负整数解非负整数解(或正整数解或正整数解)l 显然，在二元一次不定方程通解公式(2)中通过对 t 的取值范围作适当的限制，即根据题目要求，令 x0 且 y0，或 x0且y0 列出由通解公式所组成的不等式组.l 如果上面关于t的不等式组有解，说明不定方程有非负整数解(或正整数解)如果无解，说明不定方程无非负整数解(或正整数解)求非负(或正) 整数解的一般步骤：(1) 按一般方法求出通解；(2) 解上述不等式组，得出 t 的取值范围;(3) 根据 t 的取值范围，求出 t 的相应的整数值，得到不定方程的非负整数 ( 或正整数 ) 解