(i)m是任一正整数,则
(am, bm) (a, b)m
(ii)若
是a,
b的任一公因数,则
a
,
b
a, b
,
特别
a (a, b)
,
b (a, b)
1
对于两个以上整数的最大公因数问题,不妨设
a1, a2 , , an是任意n个正整数,令 (a1, a2 ) d2 , (d2 , a3 ) d3, , (dn1, an ) dn.
q及r,使得
a bq r,
b r
2
成立,而且当b是奇数时,q及r是唯一的;当b是偶数时,q及r
有可能是不唯一的。
例
当a 5, b 2时,可有
5 ( 2)( 3)(1),即q 3, r 1;
或5 ( 2)( 2)1,即q 2, r 1
证明分析:作序列
,- 3 b ,- 2 b ,- b ,0, b ,2 b ,3 b , 2 2 2 22 2
2、整除的基本定理
定理1(传递性):ab,bc ac
定理2:若a,b都是m的倍数,则ab都是m的倍数
定理3 若a1 , a2, , an都是m的倍数,q1, q2, , qn 是任意n个整数,则a1q1 a2q2 anqn是m的倍数
3、带余数除法
定理4 若a,b是两个整数,其中b 0,则存在着两个整数 q及r,使得 a bq r, 0 r b () 成立,而且q及r是唯一的。 ()式中的q及r分别叫a被b除所得的不完全商和余数。
[a1, a2 ] m2 ,[m2 , a3 ] m3, ,[mn1, an ] mn. 于是我们有
定理5 a1, a2, , an是n个正整数,则 [a1, a2 , , an ] mn.