初等数论复习知识点汇总.pptVIP

第四章 同余式 本章主要研究一次同余式，一次同余式组解存在的条件，解的数量及其求解的方法，最后讨论高次同余式解存在的条件，解的数量及其解法。 一、一元一次同余式 定理：一元一次同余式 有解的 充要条件是 且有解时， 它的解的数目是 若 有解， 则 ①化为 求解. 其中 从而求出同余式的解 ②解不定方程 例1：解同余式58x≡87(mod47) 解：∵ (47x+11x)≡(47+40)(mod47) ∴ 原余分式可化为11x≡40(mod47) ∵(11，47)=1 ∴原同余式有解且仅有一解 解不定方程 11x+47y=40 ∵ y0=6 ,x0=25是它的一个解 ∴ x≡25(mod47)是原同余式的解 解：∵ (33，141)=3 且 3|120 ∴ 原同余式有且仅有三个解 原同余式化为 11x≡40(mod47)求解。 由 例1知，x≡25(mod47) 是 11x≡40(mod47)的一个解 例2：解同余式 33x≡120 (mod141) ∴ 33x≡120(mod141)的一切解为 x≡25(mod141) , 即33x≡120(mod141)的一切解为 x≡25，72，119 (mod141) 二、 一元一次同余式组 其中 有且仅有解 则同余式组 定理：设 是两两互素的正整数， 令 例：求解同余式组 解：∵ 5，6，7，11是两两互素的正整数 ∴ 同余式组有唯一解 M=5×6×7×11=2310 ∴解同余式组的解为 ∴ 解：∵ (6，8)=2 且 2 | 10 ∴ 6x≡10(mod8) 有且仅有二个解 解 3x≡5(mod4) ? x≡-1 (mod4) ∴ 6x≡10(mod8)的解为 x≡-1，-1+4(mod8) 例：解同余式组 原同余式组同解于 或 由中国剩余定理可知同余式组 有唯一解 x≡31(mod56) 有唯一解x≡3(mod56)， 有解x≡31，3(mod56) 故同余式组 作业要求： 作业要及时完成，及时提交。 作业（网络作业、期中作业）要计入总分。 学习过程中的问题，可通过网上答疑系统提出。 考试说明： 试题类型：填空题(40%)、计算题和证明题(60%)。 考试范围1-4章：其中第1、2章各占30%，第3、4章各占20％（以光盘为准）。 试题难度不超出习题、例题、模拟试卷。 第一章 整数的整除性论 第二章 同余理论 第三章 不定方程 第四章 同余式 第一章 整数的整除性理论 本章主要从整数的整除性概念出发，介绍带余除法、辗转相除。然后以其为工具建立最大公因数和最小公倍数理论，最后介绍算术基本定理，高斯函数等。 ⑤若b|a ，a≠0 则 ④若 b|a 且 a|b， 则 |a| = |b| ① 若 c | b , b | a , 则 c | a ② b|a 的充要条件是 cb | ca ③ 若 c|a, c|b, 则对于 一般地若 m|ai（i=1 , 2 , …，n）,则 一、 整除的概念与性质 定理： ，则 使得 a=bq+r（0≤r|b|）成立, 并且q , r是唯一的。 定理：k个连续整数中有且仅有一个整数能被k整除。 定理： k个连续整数之积恒被k!所整除 例：证明6 | n(n+1)(2n+1) 证明：∵ n∈? ∴ 2 | n(n+1)(2n+1) i)若 n=3m，则 3 | n(n+1)(2n+1) ii)若 n=3m+2 ，则 n+1=3m+3 ∴ 3 | n(n+1)(2n+1) iii)若 n=3m+1, 则 2n+1=6m+2+1=6m+3 ∴ 3 | n(n+1)(2n+1) 又∵（2,3）=1 ∴ 6 | n(n+1)(2n+1) 定理1：设a, b, c是 任意三个不全为零的整数，且 a=bq+c q∈? , 则 (a , b ) = (b , c ) 定理2：任意两个正整数a , b 的任意公因数都是 (a , b) 的因数。 二、最大公因数和最小公倍数 定理3：任意两个正整数a,b，则存在整数x,y， 使得 ax+by=(a,b) 成立 (ii)若c0，c|a,c|b，则 定理4：设a,b是不全为零的整数。 (i)若 m0，则 (am,bm) = m(a,b) (iii)若 (a,b)= 1，t是任意整数， 则 (at,b)=(t,b) 定理4：设a,b是任给的两个正整数，则 (i)