
次课-整除与同余.ppt
58页第一章 整除与同余第一章 整除与同余第一章 整除与同余第一章 整除与同余主要内容• 整除的基本概念(掌握) • 素数(掌握) • 同余的概念(掌握)第一章 整除与同余1.1 整除定义1:设a,b是任意两个整数,其中b0,如果存在一个整数q,使 a = qb,则我们称b整除a,或a被b整除,记为ba,此时称 b是a的因子,a是b的倍数.例1:a=10 ,b=2则有210;若a=100,b=10有10100例2:设a是整数,a 0, 则a0. 即0是任意整 数的倍数第一章 整除与同余整除的基本性质:1. 如果ba且ab,则b = a或b = a. 2. 如果ab且bc,则ac. 3. 如果ca且cb,则cua+vb,其中u,v 是整数. 第一章 整除与同余整除的基本性质(证明): 证明: (1)由ba,根据整除定义我们可以得出:存在整数q1使 a = q1b ,同理;由ab,则存在整数q2使 b = q2a. 于是a = q1b = q2q1a .所以 q2q1 = 1, 由于q1,q2是整数,则 q2 = q1 = 1,或q2 = q1 = 1. 故b = a或b = a. 命题得证。
性质1:如果ba且ab,则b = a或b = a.第一章 整除与同余整除的基本性质(证明):证明: (2)因为ab,则存在整数q1,使 b = q1a ① 又因为bc,则存在整数q2,使 c = q2b ② 于是将①式带入②式有: c = q2b = q1q2a = qa, 其中q = q1q2. 故ac.性质2:如果ab且bc,则ac第一章 整除与同余整除的基本性质(证明):证明: (3)因为ca,则存在整数q1,使 a = q1c ① 两边同乘以整数u,有 ua=p1c (其中p1=uq1) ② 同理cb,有 vb=p2c (其中p2=vq2) ③ ②+③ 得出: pc=ua+vb 其中p=p1+p2=uq1+vq2 , 故cua+vb.性质3:如果ca且cb,则cua+vb,其中u,v是整数第一章 整除与同余整除的基本性质(补充):(1) ab -ab a-b -a-b abb≠0且ab =>a≤b 第一章 整除与同余带余除法:当两个整数不能整除时,我们有带余除法:对于a,b两个整数,其中b0,则存在唯一 q,r使得:a = bq+r,0 ≤ r 0, 则存在唯一一对整数q,r使得:a = bq+r,0 r b.第一章 整除与同余补充定理1.1(带余除法)证明 (存在性)先证满足条件的q和r是存在的。
由则q和r均为整数,由知第一章 整除与同余补充定理1.1(带余除法)(唯一性)如果存在整数q1,q2,r1,r2,0≤r1,r2 < b,使得 a=q1b+r1=q2b+r2 于是 r1-r2












