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

,第二章 同余,2022年12月6日11时54分,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年12月6日11时54分,2、同余的性质：,E,(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).,(4) 若a b (mod m)，c d (mod m) ， 则 a + c b + d (mod m) , ac bd (mod m).同余式可以相加减。,2022年12月6日11时54分,我喜欢数学,E,性质(5) 若a b (mod m)，c d (mod m) ， 则 ac bd (mod m) .同余式可以相乘。推论若a b (mod m)， 则 a k b k (mod m), k 为任意整数.同余式的数乘。,推广,2022年12月6日11时54分,性质(6),性质(7),若a =a1d, b =b1d, (m, d) =1, a b (mod m)，则 a1 b1 (mod m) .,性质(8),d为a，b及m的任一正公约数，则,若a b (mod m)，k 为正整数 ， 则 ka kb (mod km) .,2022年12月6日11时54分,性质(9),若 a b (mod m1), a b (mod m2), m= m1, m2 , 则 a b (mod m) .,性质(10) 设d 1， d | m，若a b (mod m) ， 则 a b (mod d ) .,E,New,若a b (mod m)，则 (a，m) = (b，m).,性质(11),2022年12月6日11时54分,弃九法,正整数四则运算(含乘方) 的快速验算方法,例7 用弃九法验算 2894734578 =1001865676 是否正确.,弃九法只是运算结果正确的必要条件，而非充分条件 ! 因此只能判误.,解,若通过计算，a、b的和与积分别是s与p. 而r1、r2、r3、r4 分别是a、b、s、p被 9 除所得的余数, 由同余的加减乘性质可知，如果r1 +r2与r3、 r1 r2与r4关于模 9 不同余，那么计算一定错了.,2022年12月6日11时54分,利用同余解答整除问题,例1 求7406写成十进制数时的个位数。,数 a 能被 m 整除等价于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年12月6日11时54分,二、剩余类与剩余系,定理2.2.1 设m为正整数，则全部整数可分成m个集合,记作0，1，m1，其中r (0 r m1)是由一切形如 mq + r (qZ) 的整数所组成的，并且具有下列性质：(1)每一整数必包含在而且仅在上述的一个集合中.(2)两个整数同在一个集合中的充分必要条件为这两个整数对模 m 同余。,2022年12月6日11时54分,定义2. 2 设m为正整数，则全部整数分成的 m个集合0，1，m1称为模m的剩余类,一个剩余类中任一数叫做它的同类的数的剩余。,2022年12月6日11时54分,定理2.2.2设m为正整数，则 （1）在任意取定的 m + 1 个整数中，必有两个数对模 m 同余。 （2）存在 m 个数两两对模m不同余。,完全剩余系,定义2. 3 设 m 为正整数，则从模 m 的每个剩余类中各取一个数所作成的集合，称为模 m 的一个完全剩余系.,2022年12月6日11时54分,定理2.2.4 若 a1, a2，, am 是模m的完全剩余系，,且(a, m) =1, b 为任意整数，则 aa1 +b, aa2 +b, , aam +b 也是模 m 的一个完全剩余系。,定理2.2.3设m 为正整数，整数集合 a1, a2 , , am是模 m 的完全剩余系的充分必要条件是：ai aj (mod m) ( i j ).,下面例1给出模m的另外完全剩余系绝对最小完,全剩余系.,2022年12月6日11时54分,例3 验证：11, 4, 18, 20, 32 是模 5 的一个完全剩余系。,证：只要证两两不同余即可, 也就是它们各属于不同的剩余类. 从而只要证明它们各与最小非负完全剩余系中的某一个数同余即可.,11与4, 4与1, 18与3, 20与0, 32与2分别对模5同余，所以结论成立。,2022年12月6日11时54分,定义 2.4,时，,m为质数当且仅当,设 m 是正整数，用 (m)表示不大于 m 且与 m 互质的自然数的个数称 (m)为欧拉函数,三、 欧拉函数和简化剩余系,2022年12月6日11时54分,定义 2.5,定理2.2.6设 m 是正整数，则模m的一个剩余类是与模 m互质的剩余类的充分必要条件为：这个模m的剩余类中有一数与m互质。,设 m 是正整数，若一个模m的剩余类中的数与m互质，则称这个模m的剩余类为与模m互质的剩余类。在与模 m互质的所有剩余类中，从每一类各取一数所作成的集合叫做模 m 的一个简化剩余系.,2022年12月6日11时54分,简化剩余系的充要条件,定理2.2 7 整数集合为模m的简化剩余系的充要条件是： ( i ) (ai, m) =1 ( 1i (m) ); ( ii ) 各数关于模m两两不同余,2022年12月6日11时54分,定理 2.2.10,若 m 的标准分解式是,则,欧拉函数的计算公式,推论 若 则,定理 2.2.8 若( a，m ) = 1 , x 通过模 m 的简化剩余系，则 ax 也通过模 m 的简化剩余系。,即x1, x2, xk是模m的一个简化剩余系，则ax1, ax2, , axk也是模m的简化剩余系。这里k = (m)。,2022年12月6日11时54分,欧拉函数 (m) 的计算,将,代入定理中的公式，就有,特别地，对于质数 p，有,例 4计算 (588000) 解：因 58800025 3 53 7，故由公式可得, (588000) (25 24) (31) (53 52) (72 7)=19200.,2022年12月6日11时54分,四欧拉定理,定理 2.3.1 ( 欧拉定理) 若为大于1的整数， a为整数且( a ，m) = 1, 则,应用实例,例5 求112001除以60的余数.解:又(11, 60)=1,由欧拉定理得1116 1(mod 60),故11161251 (mod 60), 112001 11 (mod 60).,一次同余方程,定义 3. 1,例如同余方程x3 + 2x120 (mod5),定义3.2 如果整数 a 满足 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 (mod6),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 )的唯一解为,一次同余方程有解的判定,定理3.1.3 设m为正整数， a, b是整数， (a, m)=d，则同余方程 axb (mod m) 有解的充分必要条件为 d | b.,定理3. 1. 4 设m为正整数, a为整数, (a, m)=d，,d | b，则同余方程 ax b (mod m) 恰有 d 个解,一次同余方程有解的解法,根据同余性质，施行适当的变形求解ab(modm):变形(1)：加上或减去模的倍数，推广的加减变形， 即 ab+mk (mod m);变形(2)：移项变形， 由 ab+c(mod m) 可得 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),二同余变形法（系数消去法）,例 求解同余方程：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),x 14 (mod 15),或解: 3x3 (mod 5), x1 4 (mod 5),3组合数法,定理 3. 1. 5 若p为质数,且0 a p, 则,为同余方程ax b (mod p) 的唯一解.,例3 解下列同余方程：7x8(mod 11);,解: 由11是质数, 且711, 因而 由公式得,同余方程组,本节讨论一次同余方程组（解的存在性、求解方法与公式），因 ax+b0 或 axb (mod m) 可以通过求解转化为xc (mod m) , 故我们只讨论,其中求解问题。,定理3.2.2 (孙子定理或中国剩余定理) :,这里Mi是同余式 MiMi 1 (mod mi ) 的解, i = 1 ,2 , , n.,x M1 M1 b1 + M2 M2 b2 + + MnMnbn (mod m) (2),恰有一整数解:,若n2 , m1 , m2 , , mn 是两两互质的n个正整数，令 m= m1 m2 mn = m1 M1 = m2 M2 = mnMn ，则同余方程组,例 韩信点兵,有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数.,解设 x 是所求兵数，则依题意，得,此同余方程组模两两互质，显然有解，且可运用孙子定理求解，过程也比较简捷 。,它们两两互素，b1 =1, b2 =5, b3 =4, b4 =10. 因此有 M = 56711= 2310, M1 = M /m1 = 462, M2 = M /m2 = 385, M3 = M /m3 = 330, M4 = M /m4 = 210.,这里 m1=5 , m2=6, m3=7, m1=11,解下列同余式,得,即 x = 2111+2310 t ( t = 0, 1, 2, ).,第四章 不定方程,不定方程是指未知数个数多于方程的个数，且未知数受到某种条件限制（例如要求整数解，非负整数解等）的方程。,整系数方程 ax + byc 叫做二元一次不定方程，这里a，b，c都是整数，且ab0,二元一次不定方程,定理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+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).,二元一次不定方程特解的求法,方法一 转化为等价的同余方程,方法二 辗转相除法,定理4.1.1的充分性证明是构造性证明，给出了求方程 ax + byc 的一个特解的方法：辗转相除法.若方程有解，则可化为 ax + by c, (a, b) = 1，必存在整数M，N，使 aM + bN 1 ( ）这里的M、N经辗转相除法求出;然后在()式两边同时乘以c，得 acM + bcN c.,因此不定方程ax + byc的一个整数解就是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)的一个整数解的方法不够简便；对于某些二元一次不定方程来说，运用整数分离法求解比较简捷,例 3 判断不定方程21x+57y639是否有整数解，如果有，请求出它的一个整数解,注意到x为整数, 通过观察与估算知 y = 2 时上面的分式为1, x有整数解, 由此得,为方程的解.,若不能观察到以上结果,可设,用较小的系数7去除上式, 于是有：,继续用上面的方法, 用较小的系数5去除上式, 得,可观察到u=1时y有整数解.,从而仍然能得出上述的一组解.,不定方程的通解,定理4.1.2 如果(a, b)=1, 且x x0，y y0是不定方程ax + byc（1）的一个解，那么它的一切解都可表示为,这里 t 为任意整数。,通解公式的特点：,公式(2)称为二元一次不定方程(1)的通解公式.其特点是: (1) 公式中 x，y 的表达式的第一项 x0 ，y0 是方程 (1) 的一个解 (称为特解)； (2) 公式中 x，y 的表达式的第二项为任意整数 t 乘以不定方程 (1) 的系数或系数的相反数且只要符号保持相反就可以,定理4.1.2告诉我们什么?,(t为任意整数).,对于二元一次不定方程(1)，只须用适当方法(观察法，同余法，辗转相除法或整数分离法) 找到它的一组整数解x= x0，y=y0,那么就可以找到方程(1)的一切整数解(通解),不定方程的非负整数解(或正整数解)的求法,实际应用中常常求不定方程的非负整数解(或正整数解) 显然，在二元一次不定方程通解公式(2)中通过对 t 的取值范围作适当的限制，即根据题目要求，令 x0 且 y0，或 x0且y0 列出由通解公式所组成的不等式组. 如果上面关于t的不等式组有解，说明不定方程有非负整数解(或正整数解)如果无解，说明不定方程无非负整数解(或正整数解),求非负(或正) 整数解的一般步骤：,(1) 按一般方法求出通解；(2) 解上述不等式组，得出 t 的取值范围;(3) 根据 t 的取值范围，求出 t 的相应的整数值，得到不定方程的非负整数 ( 或正整数 ) 解,