作业要求： 作业要及时完成，及时提交。 作业（网络作业、期中作业）要计入总分。 学习过程中的问题，可通过网上答疑系统提出。 考试说明：

Presentation on theme: "作业要求： 作业要及时完成，及时提交。 作业（网络作业、期中作业）要计入总分。 学习过程中的问题，可通过网上答疑系统提出。 考试说明："— Presentation transcript:

1 作业要求： 作业要及时完成，及时提交。 作业（网络作业、期中作业）要计入总分。 学习过程中的问题，可通过网上答疑系统提出。 考试说明： 试题类型：填空题(40%)、计算题和证明题(60%)。 考试范围1-4章：其中第1、2章各占30%，第3、4章各占20％（以光盘为准）。 试题难度不超出习题、例题、模拟试卷。

2 第一章 整数的整除性论 第二章 同余理论 第三章 不定方程 第四章 同余式

3 第一章 整数的整除性理论 本章主要从整数的整除性概念出发，介绍带余除法、辗转相除。然后以其为工具建立最大公因数和最小公倍数理论，最后介绍算术基本定理，高斯函数等。

4 一、 整除的概念与性质 ① 若 c | b , b | a , 则 c | a ② b|a 的充要条件是 cb | ca ③ 若 c|a, c|b, 则对于 一般地若 m|ai（i=1 , 2 , …，n）,则 ④若 b|a 且 a|b， 则 |a| = |b| ⑤若b|a ，a≠0 则

5 定理： ，则 使得 a=bq+r（0≤r<|b|）成立, 并且q , r是唯一的。 定理：k个连续整数中有且仅有一个整数能被k整除。 定理： k个连续整数之积恒被k!所整除

6 例：证明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 又∵（2,3）=1 ∴ 6 | n(n+1)(2n+1)

7 二、最大公因数和最小公倍数 定理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) 成立

8 定理4：设a,b是不全为零的整数。 (i)若 m>0，则 (am,bm) = m(a,b) (ii)若c>0，c|a,c|b，则 (iii)若 (a,b)= 1，t是任意整数， 则 (at,b)=(t,b)

9 定理4：设a,b是任给的两个正整数，则 (i) a , b的所有公倍数都是[a,b]的倍数。 (ii)[a,b](a,b)=ab 推论：若(a,b)=1,则[a,b]=ab 定理5：设正整数m是a, b的一个公倍数，则

10 例：如果(a , b)=1，则 (a-b ,a+b) = 1 或 2
证明：设 (a-b , a+b)= d 则 d | a-b, d | a+b ⇒ d | a-b+a+b , d | a-b-(a+b) 即 d | 2a , d | 2b ⇒ d | (2a , 2b) ⇒ d | 2(a , b) ∵ (a , b) = ∴ d | 2 ⇒ d=1 或 d=2

11 三、整数的唯一分解定理 (算术基本定理) 其中 定理：对于任一大于1的整数a，除因数的顺序 外都能唯一分解成： 且(1)d是a的正因数的充分必要条件是 (0 ≤ βi≤αi i = 1, 2, …, k) (2) a 的正因数的个数为 T(a)=(α1+1)(α2+1)…(αk+1) (αi +1)

12 (3) a的一切正因数之和 T(a)为a的一切正因数的个数。 (4) a 的一切正因数之积为

13 四、高斯函数 [x] 定理：若x是正实数，n∈+，则不大于x，且为 n的倍数的自然数的个数是 定理：在n!的标准分解式中素因数p的指数是
p(n!)

14 例：求200！标准分解式中素因数7的指数。 解：7(200!) = = 32 即 200! 的标准式中素因数7的指数为32。

15 第二章 同余理论 本章主要介绍同余的概念及其基本性质，完全剩余系和互素剩余系，以及著名的欧拉定理、费马定理和威尔逊定理。

16 一、同余概念和基本性质 定理1：整数a,b关于模m同余的充要条件是m|a-b 定理2：若 a1≡b1(modm)，a2≡b2(modm) 则 (1) a1+a2≡b1+b2(modm) (2) a1-a2≡b1-b2(modm) (3) a1a2≡b1b2(modm)

17 推论：若ak≡bk(modm) k=1,2,…,n 则 (1) (2) 推论：若a≡b(modm)，则an≡bn(modm) n∈+ 定理：若ac≡bc(modm)且(c，m)=1, 则a≡b(modm)

18 定理:若m1>0，m1|m且a≡b(modm)则a≡b(modm1)
定理：若c>0，则a≡b(modm) ac≡bc(modmc) 定理：若a≡b(modmi) (i=1，2，…, n)， 则a≡b(mod[m1，…,mn]) 定理: 若ac≡bc(modm)且(c，m)=d， 则a≡b(mod )

19 例：求7除4750的余数。 解：∵47≡-2(mod7) ∴ 4750≡(-2)50(mod7) ≡250(mod7) ≡23×16+2(mod7) ≡(23)16·22(mod7) ≡816·22(mod7) ≡1·22(mod7) ≡4(mod7) ∴ 7除4750的余数为4。

20 二、 完全剩余类和完全剩余系 定理：k个整数a1，a2，…，ak形成模m的完全剩 余系的充要条件是：
(1)k=m (2)ai≢aj(modm) ( i≠j ) 定理：若(a，m)=1,∀b∈，则当x通过模m的完 全剩余系时，则ax+b也通过模m的完全剩余系。

21 例：问0,2，22，…，210是否构成模11的完全剩余系？ 解：0，2，22=4，23=8，24≡5(mod11) 25≡2×5(mod11)≡10(mod11) 26≡10×2(mod11)≡9(mod11) 27≡7(mod11) 28≡3(mod11) 29≡6(mod11) 210≡6×2(mod11) ≡1(mod11) 是 0，1，2，…, 10 的一个排列。 ∴ 0,21，22，23，…,210 能构成模11的 一组完全剩余系。

22 三、互素剩余类和互素剩余系。 定理：k个整数a1，a2，…，ak构成模m的互素 剩余系的充要条件是
(1) k=φ(m) (2) ai≢aj (modm)(i≠j) (3) (ai, m)= (i=1，2，…,φ( m)) 定理：若 (a,m)=1，x通过模m的互素剩余系， 则ax也通过模m的互素剩余系。

23 四、 欧拉定理、费马定理和威尔逊定理 定理:(欧拉定理)若 (a,m)=1，则aφ(m) ≡ 1(modm)
四、 欧拉定理、费马定理和威尔逊定理 定理:(欧拉定理)若 (a,m)=1，则aφ(m) ≡ 1(modm) 推论:(费马定理)若p为素数,(a，p)=1, 则ap-1≡1(modp) 推论：若p为素数，∀a∈， 则 ap≡a(modp) 定理：(威尔逊定理)整数p是素数的充要条件 是(p-1)! ≡ -1(modp)

24 例：假定a是任意整数，求证 或 分析：对于任意的任意整数a，用模3分类。

25 为正整数， 例：设 证明 证明： 同理

26 第三章 不定方程 不定方程是指未知数的个数多于方程的个数，而且未知量又受某种限制(如正整数或整数解)的方程或方程组。
第三章 不定方程 不定方程是指未知数的个数多于方程的个数，而且未知量又受某种限制(如正整数或整数解)的方程或方程组。 这一章主要讨论一次不定方程整数解存在的条件，解的结构及解法，还讨论特殊的二次不定方程的解结构及解法。

27 一、二元一次不定方程 定理：不定方程ax+by=c有整数解的充要条件是 d|c，其中 d=(a,b)，并且当x=x0 , y=y0是它的一个解时，则它的一切解可以表成 (t=0，±1，±2，…)

28 二、多元一次不定方程 定理：n元一次不定方程a1x1+ … +anxn=b 有整数解的充要条件是 (a1，a2，…, an) | b

29 然后消去t2，t3，…，tn-1即 可。 可转化为求解:

30 三、勾股数 定理1：不定方程 uv=w2，(u,v)=1 的一切正整数 解可以表成 u=a2，v=b2，w=ab，
其中 a>0，b>0，(a,b)=1 定理2：不定方程x2+y2=z2满足x>0，y>0，z>0， (x,y)=1，2|x的一切整数解可表为 x=2ab，y=a2-b2，z=a2+b2 其中a>b>0，(a,b)=1，a,b一奇一偶。

31 定理3：不定方程x2+2y2=z2满足(x,y)=1的一切正
整数解可以表为x=|a2-2b2|， y=2ab，z=a2+2b2， 其中a>0，b>0，2∤a，(a,b)=1

32 第四章 同余式 本章主要研究一次同余式，一次同余式组解存在的条件，解的数量及其求解的方法，最后讨论高次同余式解存在的条件，解的数量及其解法。

33 一、一元一次同余式 定理：一元一次同余式 有解的 充要条件是 且有解时， 它的解的数目是

34 若 有解， 则 ①化为 求解. 其中 从而求出同余式的解 ②解不定方程

35 例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)是原同余式的解

36 例2：解同余式 33x≡120 (mod141) 解：∵ (33，141)=3 且 3|120 ∴ 原同余式有且仅有三个解 原同余式化为 11x≡40(mod47)求解。 由 例1知，x≡25(mod47) 是 11x≡40(mod47)的一个解

37 ∴ 33x≡120(mod141)的一切解为 x≡25(mod141) , 即33x≡120(mod141)的一切解为 x≡25，72，119 (mod141)

38 二、 一元一次同余式组 其中 有且仅有解 则同余式组 定理：设 是两两互素的正整数， 令

39 例：求解同余式组 解：∵ 5，6，7，11是两两互素的正整数 ∴ 同余式组有唯一解 M=5×6×7×11=2310

40 ∴解同余式组的解为 ∴

41 例：解同余式组 解：∵ (6，8)=2 且 2 | 10 ∴ 6x≡10(mod8) 有且仅有二个解 解 3x≡5(mod4) ⇒ x≡-1 (mod4) ∴ 6x≡10(mod8)的解为 x≡-1，-1+4(mod8)

42 原同余式组同解于 或 由中国剩余定理可知同余式组 有唯一解 x≡31(mod56) 有唯一解x≡3(mod56)， 有解x≡31，3(mod56) 故同余式组