中国科学技术大学：《离散数学》课程教学资源（PPT课件讲稿）第二章 数论基础——同余与同余式

第二章同余与同余式 o同余的概念与基本性质 o同余方程组的求解方法 o线性同余方程、高次同余方程的求解 o原根和指数 o应用

第二章 同余与同余式 同余的概念与基本性质 同余方程组的求解方法 线性同余方程、高次同余方程的求解 原根和指数 应用

第二章同余与同余式 o在日常生活中,有时我们注意的常常不是某些整数,而 是这些整数用某一个固定的整数去除所得到的余数 o例如本月2日是星期3,那么9日,16日,都是星期3,这 是因为它们用7除后得到的余数都是2 o在我国古代的干支纪年也是这样的,它是以60作为除 数的纪年法 o这样,在数学中就产生了同余的概念 o同余概念是 Gauss在1800年前后创立的

第二章 同余与同余式  在日常生活中,有时我们注意的常常不是某些整数,而 是这些整数用某一个固定的整数去除所得到的余数.  例如本月2日是星期3,那么9日,16日,…都是星期3,这 是因为它们用7除后得到的余数都是2  在我国古代的干支纪年也是这样的,它是以60作为除 数的纪年法.  这样,在数学中就产生了同余的概念.  同余概念是Gauss在1800年前后创立的

2.0同余定义和基本性质 定义1给定一正整数m,若用m去除两个整数a和b所得 余数相同,则称a与b为对模m同余,记作a= b(mod); 若余数不同,则称a与b为对模m不同余 oa≡b(modm)ifml(a-b) oa≡0(modm) iff m a o性质: ①自反性:a≡ a(mod n) ②对称性:若a= b(modn),则b≡ a(mod m) ③传递性:若a=b(modm),b≡c(modm),则: a≡ c(mod n) o可见,同余关系是等价关系

2.0 同余定义和基本性质 定义1 给定一正整数m, 若用m去除两个整数a和b所得 余数相同, 则称a与b为对模m同余, 记作ab(mod m); 若余数不同, 则称 a与b为对模m不同余。 ab(mod m) iff m|(a-b). a0(mod m) iff m| a.  性质: ①自反性: aa (mod m). ②对称性: 若ab(mod m), 则 ba(mod m). ③传递性: 若ab(mod m), bc(mod m), 则: ac(mod m).  可见, 同余关系是等价关系

2.0同余式定义和基本性质 定理1若a= b(mod m),c≡ d(mod m),则: ①ax+cy≡bx+ dy(mod n),其中x和y为任给整数 ②ac≡ bd(mod n) 1)设a≡b(modm,c是任意整数则ac ≡bc(modm) 2)设a≡b1(modm)(=1,2,,n,n>2),则 l1a anb1b2…,bn(modm ③a≡b"modm),其中n>0 ④f(a)≡f(b)modm),其中f(x)为任意的一个整系数 多项式

2.0同余式定义和基本性质 定理1 若ab(mod m), cd(mod m), 则: ① ax+cy  bx+dy(mod m), 其中x和y为任给整数. ② ac  bd(mod m). 1) 设a ≡ b (modm), c是任意整数.则ac ≡bc(modm). 2) 设ai≡ bi (modm)(i =1,2,…,n, n>2),则 a1a2…an ≡b1b2…bn (modm). ③ a n  bn(mod m), 其中 n＞0. ④ f(a) f(b)(mod m), 其中f(x)为任意的一个整系数 多项式

同余在算术里的两个应用: 应用1检查因数的一些方法 一整数能被3(9)整除if它的十进位数码的和能被 3(9)整除 o正整数a=an1000+an1000+….+ao,0≤a<1000则 7(或11,或13)整除aif7(或11,或13)整除(a+a2 +…)-(a1+ag3+.)

同余在算术里的两个应用： 应用1——检查因数的一些方法  一整数能被3(9)整除 iff 它的十进位数码的和能被 3(9)整除.  正整数a=an1000n+an-11000n-1+ … +a0 , 0≤ai<1000, 则 7(或11,或13)整除a iff 7(或11,或13)整除(a0 + a2 + …)-(a1 + a3 + …)