第二次课 整除与同余

,则?q2 = q1 = 1,或q2 = q1 = 1.?故b = a或b = a.?命题得证。Р性质1:如果ba且ab,则b = a或b = a.Р整除的基本性质(证明):Р证明:?(2)因为ab,则存在整数q1,使?b = q1a ①?又因为bc,则存在整数q2,使?c = q2b ②?于是将①式带入②式有:?c = q2b = q1q2a = qa,?其中q = q1q2.?故ac.Р性质2:如果ab且bc,则acР整除的基本性质(证明):Р证明:?(3)因为ca,则存在整数q1,使?a = q1c ①?两边同乘以整数u,有?ua=p1c (其中p1=uq1) ②?同理cb,有?vb=p2c (其中p2=vq2) ③?②+③得出:?pc=ua+vb?其中p=p1+p2=uq1+vq2 ,?故cua+vb.Р性质3:如果ca且cb,则cua+vb,其中u,v是整数Р整除的基本性质(补充):Р(1) ab<=> -ab<=> a-b <=> ?-a-b <=> abРb≠0且ab =>a≤bР带余除法:Р当两个整数不能整除时,我们有带余除法:Р对于a,b两个整数,其中b0,则存在唯一?q,r使得:? a = bq+r,0 ≤ r < |b|.?r称为a被b除得到的余数.?显然当r = 0时,ba.Р证明Р带余除法:Р例3 1)a = –37, b= 5,则?–37 = (8)5+3,r = 3.?2)a = 67,b= 7,则?67 = (9)( 7)+4,r = 4.Р最大公因子(定义)Р定义2:?1)设a,b是两个整数,如果整数ca且cb,则c称为a,b的公因子.?2)设c0是两个不全为零的整数a,b的公因子,如果a,b的任何公因子都整除c,则c称为a,b的最大公因子,记为c= (a,b).