中国科学技术大学：《离散数学》课程教学资源（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 + …)

同余的算术应用1 ☆正整数a能被9整除if9整除a的十进制表示各数字 的和 证明若a=>a.10,则由 10}=1(mod9)(i=1,2,,n) 和定理1④可得 a=oa)(mod 9) 注:因为10≡1(mod3),同理,一个整数能被3整除的必 要充分条件是它的10进位数码的和能被3整除

* 正整数a能被9整除 iff 9整除a的十进制表示各数字 的和． 证明 若 , 则由 10i1(mod 9) (i=1,2,…,n) 和定理 1④可得: 注：因为10≡1(mod3)，同理, 一个整数能被3整除的必 要充分条件是它的10进位数码的和能被3整除. = =  n i i a ai 0 10 =  n i a ai 0 ( )(mod 9) 同余的算术应用1

同余的算术应用1 正整数a能被7(或11,或13)整除ifrf7(或11,或13)整 除的定理进制表示各数字的交错和a=∑(-1)a 证明:因为1000与-1对模7(或11,或13)同余, 由同余性质,a=∑(-1)amod7)(或modl,或 mod13). 所以,结论得证

同余的算术应用1 ** 正整数a能被7(或11，或13)整除 iff 7(或11，或13) 整 除a的定理十进制表示各数字的交错和 ． 证明：因为1000与-1对模7(或11，或13)同余， 由同余性质， (或mod11，或 mod13). 所以 ，结论得证。 （-1）（mod7） 0 i =  n i a ai = = n i a ai 0 i （-1）

同余的算术应用2—弃九法 o*证明了“弃九法”(弃九验算法):把一个数的各 位数字相加,直到和是一个一位数(和是9,要减去 9得0),这个数就叫做原来数的弃九数.且一个数 的弃九数与其模9的余数相等。 o利用这种方法可以验算较大整数的加法、减法、乘 法运算的结果是否正确,也可验算除法,但需转化 成乘法

同余的算术应用2 ——弃九法  *证明了“弃九法”（弃九验算法）：把一个数的各 位数字相加，直到和是一个一位数（和是9，要减去 9得0），这个数就叫做原来数的弃九数．且一个数 的弃九数与其模9的余数相等。  利用这种方法可以验算较大整数的加法、减法、乘 法运算的结果是否正确，也可验算除法，但需转化 成乘法

弃九法 例1验算851+346=1198 解:先分别求出两个加数的弃九数与和的弃九数 851、346的弃九数分别是5,4,1198的弃九数1 两个加数的弃九数相加得4+5=9,弃掉9后是0,而题 目中和的弃九数是1,可以说这道题一定错误。 注:利用弃九法检验运算的结果是否正确时, >如果等号两边的九余数不相等,那么这个算式肯 定不正确; ≯如果等号两边的九余数相等,那么还不能确定算 式是否正确,因为九余数只有0,1,2,…,8九种 凊况,不同的数可能有相同的九余数。所以用弃九 法检验运算的正确性,只是一种粗略的检验

弃九法 例1 验算 851+346=1198． 解： 先分别求出两个加数的弃九数与和的弃九数． 851、346的弃九数分别是5，4，1198的弃九数1． 两个加数的弃九数相加得4+5=9，弃掉9后是0，而题 目中和的弃九数是1，可以说这道题一定错误。 注：利用弃九法检验运算的结果是否正确时， ➢ 如果等号两边的九余数不相等，那么这个算式肯 定不正确； ➢ 如果等号两边的九余数相等，那么还不能确定算 式是否正确，因为九余数只有0，1，2，…，8九种 情况，不同的数可能有相同的九余数。所以用弃九 法检验运算的正确性，只是一种粗略的检验

弃九法 例2求证1997×57≠113828 证明由于1997=1+9+9+7=8(mod9) 57=5+7≡3mod9) 113828≡1+1+3+8+2+8=5(mod9) o但是,8×3=24,而24≠5(mod9),得证

弃九法 例2 求证 1997×57≠113828. 证明 由于19971＋9＋9＋78 (mod 9) 57 5＋7  3(mod 9) 113828  l+1+3+8+2+8  5(mod 9)  但是, 8×3=24, 而24≠5(mod 9), 得证