4
若r1 = 0, 則(a, b) = b.
若r1 6= 0, 則又可用r1去除b得b = r1q2 + r2, 0 6 r2 < r1.
若r2 = 0, 則(a, b) = (b, r1) = r1.
若r2 6= 0, 再用r2去除r1得r1 = r2q3 + r3, 0 6 r3 < r2.
如此繼續(xù)下去, 由于b > r1 > r2 > r3 > · · ·以及ri(i = 1, 2, · · ·)是非負整數(shù), 則一定在進行到某一次
時, 例如第n + 1次得到rn+1 = 0. 但由于rn 6= 0, 則有(a, b) = (b, r1) = (r1, r2) = · · · = (rn?1, rn) = rn.
用此法還可以求(5)中形如ax + by的最小正整數(shù)d = ax0 + by0.
2. 公倍數(shù)和最小公倍數(shù)
(1)若a1|b, a2|b, · · · , an|b, 則b稱為a1, a2, · · · , an的公倍數(shù). a1, a2, · · · , an的所有公倍數(shù)中最小的一個
稱為a1, a2, · · · , an的最小公倍數(shù). 記作[a1, a2, · · · , an].
(2)若a1, a2, · · · , an的標準分解式為a1 =
Qm
i=1
p
αi
i
, a2 =
Qm
i=1
p
βi
i
, · · · , an =
Qm
i=1
p
δi
i
, 其中pi為質數(shù), αi
, βi
,
· · · , δi為非負整數(shù), i = 1, 2, · · · , m, 則[a1, a2, · · · , an] = Qm
i=1
p
ri
i
, 其中ri = max{αi
, βi
, · · · , δi}.
(3)a1, a2, · · · , an的最小公倍數(shù)是它們的任一公倍數(shù)的約數(shù).
(4)[a, b] = ab
(a, b)
.
6 互質數(shù)、費馬小定理和孫子定理
1. 互質數(shù)
(1)若(a1, a2, · · · , an) = 1, 就叫做a1, a2, · · · , an互質(也叫做互素). 這n個數(shù)叫互質數(shù)(互素數(shù)).
特別地, 1和任何整數(shù)互質; 相鄰兩個整數(shù)互質; 相鄰兩個奇數(shù)互質; 對質數(shù)p, 若p不能整除a, 則p與a互
質.
(2)若(a, b) = 1, 則(a ± b, a) = 1, (a ± b, ab) = 1.
(3)若(a, b) = 1, a|bc, 則a|c.
(4)若a|c, b|c, (a, b) = 1, 則ab|c.
(5)若(a, b) = 1, 則(b, ac) = (b, c).
(6)若(a, b) = 1, c|a, 則(c, b) = 1.
(7)若(a, b) = 1, 則(a, bk
) = 1.
(8)若a1, a2, · · · , am中的每一個與b1, b2, · · · , bn中的每一個互質, 則(a1a2 · · · am, b1b2 · · · bn) = 1.
2. 歐拉函數(shù)
定義: 小于m且與m互質的正整數(shù)的個數(shù)叫做歐拉(Euler)函數(shù), 記作?(m).