发布时间 : 星期六 文章4-6数论教案更新完毕开始阅读
[a, b] =
ab。 (a,b)证明 设m是a和b的一个公倍数，那么存在整数k1，k2，使得m = ak1，m = bk2，因此
ak1 = bk2 。 (1)
于是
abk1?k2。 (a,b)(a,b)ab,)= 1，所以由第三节定理4得到 由于((a,b)(a,b)b|k1，即k1?bt， (a,b)(a,b)其中t是某个整数。将上式代入式(1)得到
abm =t 。 (2)
(a,b)另一方面，对于任意的整数t，由式(2)所确定的m显然是a与b的公倍数，因此a与b的公倍数必是式(2)中的形式，其中t是整数。当t = 1时，得到最小公倍数
ab[a, b] =。
(a,b)证毕。
推论1 两个整数的任何公倍数可以被它们的最小公倍数整除。 证明 由式(2)可得证。证毕。
这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数。 推论2 设m，a，b是正整数，则[ma, mb] = m[a, b]。 证明 由定理2及第三节定理2的推论得到
m2abm2abmab??[ma, mb] == m[a, b]。
(ma,mb)m(a,b)(a,b)证毕。
定理3 对于任意的n个整数a1, a2, ?, an，记
[a1, a2] = m2，[m2, a3] = m3，?，[mn?2, an?1] = mn?1，[mn?1, an] = mn，
则
[a1, a2, ?, an] = mn。
证明 我们有
mn = [mn?1, an] ? mn?1?mn，an?mn，
mn?1 = [mn?2, an?1] ? mn?2?mn?1?mn，an?mn，an?1?mn?1?mn， mn?2 = [mn?3, an?2] ? mn?3?mn?2?mn，an?mn，an?1?mn，an?2?mn，
? ?
m2 = [a1, a2] ? an?mn，?，a2?mn，a1?mn，
即mn是a1, a2, ?, an的一个公倍数。
另一方面，对于a1, a2, ?, an的任何公倍数m，由定理2的推论及m2, ?, mn的定义，得
m2?m，m3?m，?，mn?m。
即mn是a1, a2, ?, an最小的正的公倍数。证毕。
推论 若m是整数a1, a2, ?, an的公倍数，则[a1, a2, ?, an]?m 。 证明 留作习题。
定理4 整数a1, a2, ?, an两两互素，即
(ai, aj) = 1，1 ? i, j ? n，i ? j
的充要条件是
[a1, a2, ?, an] = a1a2?an 。 (3)
证明 必要性 因为(a1, a2) = 1，由定理2得到
aa[a1, a2] =12= a1a2 。
(a1,a2)由(a1, a3) = (a2, a3) = 1及第三节定理4推论3得到
9
(a1a2, a3) = 1，
由此及定理3得到
[a1, a2, a3] = [[a1, a2], a3] = [a1a2, a3] = a1a2a3 。
如此继续下去，就得到式(3)。
充分性 用归纳法证明。当n = 2时，式(3)成为[a1, a2] = a1a2。由定理2
aaa1a2 = [a1, a2] =12? (a1, a2) = 1，
(a1,a2)即当n = 2时，充分性成立。
假设充分性当n = k时成立，即
[a1, a2, ?, ak] = a1a2?ak ? (ai, aj) = 1，1 ? i, j ? k，i ? j。
对于整数a1, a2, ?, ak, ak + 1，使用定理3中的记号，由定理3可知
[a1, a2, ?, ak, ak + 1] = [mk, ak + 1]。 (4)
其中mk = [a1, a2, ?, ak]。因此，如果
[a1, a2, ?, ak, ak + 1] = a1a2?akak + 1，
那么，由此及式(4)得到
mkak?1[a1, a2, ?, ak, ak + 1] = [mk, ak + 1] == a1a2?akak + 1，
(mk,ak?1)即
mk= a1a2?ak ，
(mk,ak?1)显然mk ? a1a2?ak，(mk, ak + 1) ? 1。所以若使上式成立，必是
(mk, ak + 1) = 1， (5)
并且
mk = a1a2?ak 。 (6)
由式(6)与式(5)推出
(ai, ak + 1) = 1，1 ? i ? k； (7)
由式(6)及归纳假设推出
(ai, aj) = 1，1 ? i, j ? k，i ? j 。 (8)
综合式(7)与式(8)，可知当n = k ? 1时，充分性成立。由归纳法证明了充分性。证毕。
定理4有许多应用。例如，如果m1, m2, ?, mk是两两互素的整数，那么，要证明m = m1m2?mk整除某个整数Q，只需证明对于每个i，1 ? i ? k，都有mi?Q。这一点在实际计算中是很有用的。对于函数f(x)，要验证命题“m?f(n)，n?Z”是否成立，可以用第二节例5中的方法，验证“m?f(r)，r = 0, 1, ?, m ? 1”是否成立。这需要做m次除法。但是，若分别验证“mi?f(ri)，ri = 0, 1, ?, mi ? 1，1 ? i ? k”是否成立，则总共需要做m1 ? m2 ? ? ? mk次除法。后者的运算次数显然少于前者。
例1 设a，b，c是正整数，证明：[a, b, c](ab, bc, ca) = abc 。 解 由定理3和定理2有
[a,b]c[a, b, c] = [[a, b], c] =， (9)
([a,b],c)由第三节定理5和定理2的推论，
(ab, bc, ca) = (ab, (bc, ca)) = (ab, c(a, b))
abc)?(ab[a,b],abc)?ab([a,b],c)。 (10) =(ab,[a,b][a,b][a,b]联合式(9)与式(10)得到所需结论。
例2 对于任意的整数a1, a2, ?, an及整数k，1 ? k ? n，证明：
[a1, a2, ?, an] = [[a1, ?, ak],[ak + 1, ?, an]]
解 因为[a1, a2, ?, an]是a1, ?, ak, ak + 1, ?, an的公倍数，所以由定理2推论，推出
[a1, ?, ak]?[a1, a2, ?, an]， [ak + 1, ?, an]?[a1, a2, ?, an]，
再由定理3推论知
[[a1, ?, ak], [ak + 1, ?, an]]?[a1, a2, ?, an]。 (11)
另一方面，对于任意的ai（1 ? i ? n），显然
ai?[[a1, ?, ak], [ak + 1, ?, an]]， 10
所以由定理3推论可知
[a1, a2, ?, an]?[[a1, ?, ak], [ak + 1, ?, an]]，
联合上式与式(11)得证。
例3 设a，b，c是正整数，证明：
[a, b, c][ab, bc, ca] = [a, b][b, c][c, a]。
解 由定理2推论2及例2，有
[a, b, c][ab, bc, ca] = [[a, b, c]ab, [a, b, c]bc, [a, b, c]ca]
222222
= [[ab, ab, abc], [abc, bc, bc], [ac, abc, ac]]
222222
= [ab, ab, abc, abc, bc, bc, ac, abc, ac]
222222
= [abc, ab, ac, bc, ba, ca, cb]
以及
[a, b][b, c][c, a] = [[a, b]b, [a, b]c][c, a]
2
= [ab, b, ac, bc][c, a]
2
= [ab[c, a], b[c, a], ac[c, a], bc[c, a]]
222222
= [abc, ab, bc, ba, ac, ac, bc, bca]
222222
= [abc, ab, ac, bc, ba, ca, cb]，
由此得证。
习 题 四
1. 证明定理1。
2. 证明定理3的推论。
3. 设a，b是正整数，证明：(a ? b)[a, b] = a[b, a ? b]。
4. 求正整数a，b，使得a ? b = 120，(a, b) = 24，[a, b] = 144。 5. 设a，b，c是正整数，证明：
[a,b,c]2(a,b,c)2?。
[a,b][b,c][c,a](a,b)(b,c)(c,a) 6. 设k是正奇数，证明：1 ? 2 ? ? ? 9?1 ? 2 ? ? ? 9。
第五节 辗转相除法
本节要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。
定义1 下面的一组带余数除法，称为辗转相除法。 设a和b是整数，b ? 0，依次做带余数除法：
a = bq1 ? r1， 0 < r1 < |b|， b = r1q2 ? r2， 0 < r2 < r1 ，
? ?
rk ? 1 = rkqk + 1 ? rk + 1，0 < rk + 1 < rk ， (1)
? ?
rn ? 2 = rn ? 1qn ? rn， 0 < rn < rn-1 ， rn ? 1 = rnqn + 1 。
由于b是固定的，而且
|b| > r1 > r2 > ? ，
所以式(1)中只包含有限个等式。
下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计。 引理1 用下面的方式定义Fibonacci数列{Fn}：
F1 = F2 = 1，Fn = Fn ? 1 ? Fn ? 2，n ? 3，
那么对于任意的整数n ? 3，有
Fn > ? n ? 2， (2) 其中? =
1?5。 2kkk11
证明 容易验证
? 2 = ? ? 1。
当n = 3时，由
F3 = 2 >
1?5= ? 2可知式(2)成立。
假设式(2)对于所有的整数k ? n（n ? 3）成立，即
Fk > ? k ? 2，k ? n，
则
Fn + 1 = Fn ? Fn ? 1 > ? n ? 2 ? ? n ? 3 = ? n ? 3(? ? 1) = ? n ? 3? 2 = ? n? 1， 即当k = n ? 1时式(2)也成立。由归纳法知式(2)对一切n ? 3成立。证毕。
定理1(Lame) 设a, b?N，a > b，使用在式(1)中的记号，则
n < 5log10b。
证明 在式(1)中，rn ? 1，qn + 1 ? 2，qi ? 1（1 ? i ? n），因此
rn ? 1 = F2 ，
rn ? 1 ? 2rn ? 2 = F3 ，
rn ? 2 ? rn ? 1 ? rn ? F3 ? F2 = F4 ，
? ?
b ? r1 ? r2 ? Fn + 1 ? Fn = Fn + 2 ，
由此及式(2)得
b ? ?n =(即
1?5n)， 21?51?n， 25log10b ? nlog10
这就是定理结论。证毕。
定理2 使用式(1)中的记号，记
P0 = 1，P1 = q1，Pk = qkPk ? 1 ? Pk ? 2，k ? 2， Q0 = 0，Q1 = 1，Qk = qkQk ? 1 ? Qk ? 2，k ? 2，
则
aQk ? bPk = (?1)k ? 1rk，k = 1, 2, ?, n 。 (3)
证明 当k = 1时，式(3)成立。 当k = 2时，有
Q2 = q2Q1 ? Q0 = q2，P2 = q2P1 ? P0 = q2q1 ? 1，
此时由式(1)得到
aQ2 ? bP2 = aq2 ? b(q2q1 ? 1) = (a ? bq1)q2 ? b = r1q2 ? b = ?r2，
即式(3)成立。
假设对于k < m（1 ? m ? n）式(3)成立，由此假设及式(1)得到 aQm ? bPm= a(qmQm ? 1 ? Qm ? 2) ? b(qmPm ? 1 ? Pm ? 2)
= (aQm ? 1 ? bPm ? 1)qm ? (aQm ? 2 ? bPm ? 2)
m 2m 3
= (?1)?rm ? 1qm ? (?1)?rm ? 2
m 1m 1
= (?1)?(rm ? 2 ? rm ? 1qm) = (?1)?rm ，
即式(3)当k = m时也成立。定理由归纳法得证。证毕。
定理3 使用式(1)中的记号，有rn = (a, b)。 证明 由第三节定理1，从式(1)可见
rn = (rn ? 1, rn) = (rn ? 2, rn ? 1) = ? = (r1, r2) = (b, r1) = (a, b)。
证毕。
现在我们已经知道，利用辗转相除法可以求出整数x，y，使得
ax ? by = (a, b) 。 (4)
为此所需要的除法次数是O(log10b)。但是如果只需要计算(a, b)而不需要求出使式(4)成立的整数x与y，则所需要的除法次数还可更少一些。
例1 设a和b是正整数，那么只使用被2除的除法运算和减法运算就可以计算出(a, b)。 解 下面的四个基本事实给出了证明： 12