1、第一章 整除與同余1第一章 整除與同余主要內(nèi)容整除的基本概念（掌握）素數(shù)（掌握）同余的概念（掌握）21.1 整除定義1：設(shè)a，b是任意兩個整數(shù)，其中b0，如果存在一個整數(shù)q，使a = qb，則我們稱b整除a，或a被b整除，記為ba，此時稱b是a的因子，a是b的倍數(shù)例1：a=10 ,b=2則有210；若a=100,b=10有10100例2：設(shè)a是整數(shù)，a 0, 則a0 即0是任意整數(shù)的倍數(shù)3整除的基本性質(zhì)：如果ba且ab，則b = a或b = a 如果ab且bc，則ac如果ca且cb，則cua+vb，其中u，v是整數(shù) 4整除的基本性質(zhì)（證明）：證明：（1）由ba，根據(jù)整除定義我們可以得出：存在整

2、數(shù)q1使a = q1b ， 同理；由ab，則存在整數(shù)q2使b = q2a于是a = q1b = q2q1a 所以q2q1 = 1，由于q1，q2是整數(shù)，則q2 = q1 = 1，或q2 = q1 = 1故b = a或b = a命題得證。性質(zhì)1：如果ba且ab，則b = a或b = a5整除的基本性質(zhì)（證明）：證明：（2）因為ab，則存在整數(shù)q1，使b = q1a 又因為bc，則存在整數(shù)q2，使c = q2b 于是將式帶入式有：c = q2b = q1q2a = qa，其中q = q1q2故ac性質(zhì)2：如果ab且bc，則ac6整除的基本性質(zhì)（證明）：證明：（3）因為ca，則存在整數(shù)q1，使a =

3、 q1c 兩邊同乘以整數(shù)u，有ua=p1c (其中p1=uq1) 同理cb，有vb=p2c (其中p2=vq2) + 得出：pc=ua+vb其中p=p1+p2=uq1+vq2 ，故cua+vb性質(zhì)3：如果ca且cb，則cua+vb，其中u，v是整數(shù)7整除的基本性質(zhì)（補(bǔ)充）：(1) ab -ab a-b -a-b abb0且ab =ab 8帶余除法：當(dāng)兩個整數(shù)不能整除時，我們有帶余除法：對于a，b兩個整數(shù)，其中b0，則存在唯一q，r使得： a = bq+r，0 r 0，則存在唯一一對整數(shù)q，r使得： a = bq+r，0 r b56補(bǔ)充定理1.1（帶余除法）證明（存在性）先證滿足條件的q和r是存在的。 由 則q和r均為整數(shù)，由 知57補(bǔ)充定理1.1（帶余除法）（唯一性）如果存在整數(shù)q1,q2,r1,r2,0r1,r2 b,使得a=q1b+r1=q2b+r2于是r1-r2b,且r1-r2=b(q1-q2)若q