则
p p i1 i 2 12
s1, t1
，使 b
s1t
t1,|
t1
|
|t| 2
b 22
,
, 如此类推知：
sn , tn , tn2 tn1sn tn ;
sn1, tn1, tn1 tnsn1 tn1;
且
|
tn
|
|
tn1 2
|
|
tn2 22
|
|t| 2n
|b| 2n1
而 b 是一个有限数，n N, 使 tn1 0
(a, b) (b, t) (t, t1) (t1, t2 ) (tn, tn1) (tn, 0) tn ，存在其求法为：
r1 b
(a,b) rn
d | a bq1 r1 ， d | b r1q2 r2 ，┄, d | rn2 rn1qn rn (a, b) ,
即 d 是 (a, b) 的因数。
反过来 (a,b) | a 且 (a,b) | b ，若 d | (a,b), 则 d | a, d | b ，所以 (a,b) 的因数都是 a, b 的公
在整数集合 S ax by | x, y Z 中存在正整数，因而有形如 ax by 的最小整数
ax0 by0 x, y Z ，由带余除法有 ax by (ax0 by0 )q r, 0 r ax0 by0 则 r (x x0q)a ( y y0q)b S ，由 ax0 by0 是 S 中的最小整数知 r 0 ax0 by0 | ax by ax0 by0 | ax by （ x, y 为任意整数） ax0 by0 | a, ax0 by0 | b ax0 by0 | (a,b). 又有 (a,b) | a ， (a,b) | b (a,b) | ax0 by0 故 ax0 by0 (a, b) 4．若 a，b 是任意二整数，且 b 0 ，证明：存在两个整数 s，t 使得 a bs t, | t | | b | 2 成立，并且当 b 是奇数时，s，t 是唯一存在的．当 b 是偶数时结果如何
∴
p i i
|
p i i
,
pi i
|
p i i
(i 1, 2
k)
k
k
k
k
∴
pi i
pi i
，
pi i
p i i
.
i 1
i 1
i 1
i 1
∴
p p 1 2 12
pk k
| (a,b) ，又显然 (a,b) |
p1 1
p 2 2
pk k
∴
p p 1 2 12
pk k
(a, b)
，同理可得
p1 1
(2q2 ,
p2)
q2
1
但由 ( p, q) 1, q 1 知 ( p2, q2 ) 1，矛盾，故 2 不是有理数。
§4 质数·算术基本定理 1．试造不超过 100 的质数表 解：用 Eratosthenes 筛选法
（1）算出 100 10 a （2）10 内的质数为：2，3，5，7
（3）划掉 2，3，5，7 的倍数，剩下的是 100 内的素数
(a,b) (b, a bs) (a bs,b (a bs)s1)
(76501, 9719) (9719, 76501 9719 7) (8468,9719 8468) (1251,8468 1251 6) (3,1) 1
4．证明本节（1）式中的 n log b log 2
第一章 整数的可除性
§1 整除的概念·带余除法 1．证明定理 3 定 理 3 若 a1，a2， ，an 都 是 m 得 倍 数 ， q1，q2， ，qn 是 任 意 n 个 整 数 ， 则 q1a1 q2a2 qnan 是 m 得 倍 数 ． 证明： a1, a2 , an 都是 m 的倍数。 存在 n 个整数 p1, p2 , pn 使 a1 p1m, a2 p2m, , an pnm 又 q1, q2 , , qn 是任意 n 个整数 q1a1 q2a2 qnan q1 p1m q2 p2m qn pnm ( p1q1 q2 p2 qn pn )m 即 q1a1 q2a2 qnan 是 m 的整数 2．证明 3 | n(n 1)(2n 1) 证明 n(n 1)(2n 1) n(n 1)(n 2 n 1)
n(n 1)(n 2) (n 1)n(n 1) 又 n(n 1)(n 2) ， (n 1)n(n 2) 是连续的三个整数 故 3 | n(n 1)(n 2), 3 | (n 1)n(n 1) 3 | n(n 1)(n 2) (n 1)n(n 1) 从而可知 3 | n(n 1)(2n 1) 3．若 ax0 by0 是形如 ax by （x，y 是任意整数，a，b 是两不全为零的整数）的数中最 小整数，则 (ax0 by0 ) | (ax by) ． 证： a,b 不全为 0
证：由 P3§1 习题 4 知在（1）式中有
0
rn1
rn
rn1 2
rn2 22
r1 2n1
b 2n
，而 rn1
1
b 2n
, 2n
b
，
n
log2
b
log b log 2
，即
n
log log
b 2
§3 整除的进一步性质及最小公倍数
1．证明两整数 a，b 互质的充分与必要条件是：存在两个整数 s，t 满足条件 ax bt 1． 证明 必要性。若 (a,b) 1，则由推论知存在两个整数 s，t 满足： as bt (a,b) ，
p2 2
pk k
[a,b] ，i
max{i , i}
推广
设 a1
p p 11 12 12
p a p p , 1k
k
2Leabharlann 21 22 12p , 2k k
, an
p p n1 n 2 12
p nk k
(其中 p j 为质数 j 1, 2, , k, ai 为任意 n 个正整数 i 1, 2, , n, ij 0 )，
),
t1
b, 2
t1
b 2
§2 最大公因数与辗转相除法
1．证明推论 推论 4.1 a，b 的公因数与（a，b）的因数相同．
证：设 d 是 a，b 的任一公因数， d |a， d |b
由带余除法
a bq1 r1,b r1q2 r2 , , rn2 rn1qn rn , rn1 rnqn1, 0 rn1 rn rn1
2
2
2，
得证．
下证唯一性
当 b 为奇数时，设 a bs t bs1 t1 则 t t1 b(s1 s) b
而
t
b 2
, t1
b 2
t t1
t
t1
b
矛盾 故 s s1,t t1
当 b 为偶数时， s,t 不唯一，举例如下：此时 b 为整数 2
3 b 2
b 1 b 2
b
2
(
b 2
所以 (q, pn ) 1,q | an ；
又由（2）有 an pn an1 pn1q a1 pqn1 a0qn
因为 p 整除上式的右端，所以 P | a0qn ， ( p, q) 1, q 1 ，所以 (qn , p) 1, ∴p | an
故（1）的有理根为
p q
，且
p
|
a0 ,
q
|
证：作序列
3b
b b 3b
, , b , , 0, , b , ,
则 a 必在此序列的某两项之间
2
22 2
即存在一个整数 q ，使 q b a q 1 b 成立
2
2
(i) 当 q 为偶数时，若 b 0. 则令 s q ,t a bs a q b ，则有
2
2
0 a bs t a q b a q b q b t b
a
p1 1
p2 2
pn n
，i
0，i
1, 2,
,k ，
b
p 1 1
p2 2
pn n
， i
0，i
1, 2,
,k ，
则 (a,b)
p1 1
p2 2
pk k
，[a,b]
p1 1
p2 2
pk k
，
其中 i min(i , i ) ，i min(i , i ) ， i 1, 2, , k
证： i min(i , i ) ， 0 i i , 0 i i
as bt 1
充分性。若存在整数 s，t 使 as+bt=1，则 a，b 不全为 0。
又因为 (a,b) | a, (a,b) | b ，所以 (a,b | as bt) 即 (a,b) |1。
又 (a,b) 0 ，(a,b) 1
2．证明定理 3
定理 3 a1, a2 , an | a1 |,| a2 | ,| an |
2
22
2
若 b 0 则令 s q ,t a bs a q b ，则同样有 t b
2
2
2
(ii) 当 q 为奇数时，若 b 0 则令 s q 1,t a bs a q 1b ，则有
2
2
b t a bs a q 1b a q 1 b 0 t b
2
2
2
2
若 b 0 ，则令 s q 1,t a bs a q 1b ，则同样有 t b 综上所述，存在性
证：设（1）的任一有理根为 p ， ( p, q) 1, q 1 。则 q
an
(
p q
)n
an 1 (
p q
)n1
a1
p q
a0
0
an pn an1 pn1q a1 pqn1 a0qn 0