若 b 0 ，则令 s
得证． 下证唯一性 当 b 为奇数时，设 a bs t bs1 t1 则 t t1 b( s1 s ) b 而t
b b , t1 t t1 t t1 b 矛盾 故 s s1 , t t1 2 2
b 为整数 2
ax0 by0
x, y Z ，由带余除法有 ax by (ax0 by0 )q r , 0 r ax0 by0
则 r ( x x0 q )a ( y y0 q )b S ，由 ax0 by0 是 S 中的最小整数知 r 0
ax0 by0 | ax by ax0 by0 | ax by
a, b Z , b 0, s, t Z , 使 a bs t ,| t |
b 。 ， 2
s1 , t1 ，使 b s1t t1 ,| t1 | sn , tn , tn 2 tn 1sn tn ; sn 1 , tn 1 , tn 1 tn sn 1 tn 1 ;
5 / 78
《初等数论》 （闵嗣鹤、严士健编著） （第三版）习题解答
是一个整数系数多项式且 a0 ，an 都不是零，则（1）的根只能是以 a0 的因数作分子以 an 为 分母的既约分数，并由此推出 2 不是有理数． 证：设（1）的任一有理根为
p ， ( p, q ) 1, q 1 。则 q
a bs t ,
| t |
|b| 2
成立，并且当 b 是奇数时，s，t 是唯一存在的．当 b 是偶数时结果如何？ 证：作序列 ,
3b b b 3b , b , , 0, , b , , 则 a 必在此序列的某两项之间 2 2 2 2
q q 1 b a b 成立 2 2 q q , t a bs a b ，则有 2 2
2
p2 , 2q 2 p 2 , ( p 2 , q 2 ) (2q 2 , p 2 ) q 2 1 2 q
但由 ( p, q ) 1, q 1 知 ( p 2 , q 2 ) 1 ，矛盾，故 2 不是有理数。 §4 质数·算术基本定理
6 / 78
《初等数论》 （闵嗣鹤、严士健编著） （第三版）习题解答
q 1 q 1 , t a bs a b ，则有 2 2
2 / 78
(ii ) 当 q 为奇数时，若 b 0 则令 s
《初等数论》 （闵嗣鹤、严士健编著） （第三版）习题解答

b b q 1 q 1 t a bs a ba b 0 t 2 2 2 2 b q 1 q 1 综上所述，存在性 , t a bs a b ，则同样有 t 2 ， 2 2
1．试造不超过 100 的质数表 解：用 Eratosthenes 筛选法 （1）算出 100 10 a （2）10 内的质数为：2，3，5，7 （3）划掉 2，3，5，7 的倍数，剩下的是 100 内的素数 将不超过 100 的正整数排列如下： 1 11 21 31 41 51 61 71 81 91 2 12 22 32 42 52 62 72 82 92 3 13 23 33 43 53 63 73 83 93 4 14 24 34 44 54 64 74 84 94 5 15 25 35 45 55 65 75 85 95 6Байду номын сангаас16 26 36 46 56 66 76 86 96 7 17 27 37 47 57 67 77 87 97 8 18 28 38 48 58 68 78 88 98 9 19 29 39 49 59 69 79 89 99 10 20 30 40 50 60 70 80 90 100
当 b 为偶数时， s, t 不唯一，举例如下：此时
3
b b b b b b 1 b 2 ( ), t1 , t1 2 2 2 2 2
§2 最大公因数与辗转相除法 1．证明推论 4.1 推论 4.1 a，b 的公因数与（a，b）的因数相同． 证：设 d 是 a，b 的任一公因数， d |a， d |b 由带余除法
又 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)
∴ p | an
p ，且 p | a0 , q | an 。 q
假设 2 为有理数， x 2, x 2 2 0 ，次方程为整系数方程，则由上述结论，可知其 有有理根只能是
1, 2 ，这与 2 为其有理根矛盾。故 2 为无理数。
另证，设 2 为有理数 2 =
p , ( p, q ) 1, q 1 ，则 q
即 d 是 ( a, b) 的因数。
3 / 78
《初等数论》 （闵嗣鹤、严士健编著） （第三版）习题解答
反过来 ( a, b) | a 且 ( a, b) | b ，若 d | ( a, b), 则 d | a, d | b ，所以 ( a, b) 的因数都是 a , b 的公因 数，从而 a , b 的公因数与 ( a, b) 的因数相同。 2．证明：见本书 P2，P3 第 3 题证明。 3．应用§1 习题 4 证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求 法及辗转相除法实际算出（76501，9719） ． 解：有§1 习题 4 知：
证：设 [a1 , a2 , , an ] m1 ，则 ai | m1 (i 1, 2, , n)
∴ | ai || m1 (i 1, 2, , n) 又设 [| a1 |,| a2 |, ,| an |] m2
则 m2 | m1 。反之若 | ai || m2 ，则 ai | m2 ， m1 | m2 从而 m1 m2 ，即 [a1 , a2 , , an ] = [| a1 |,| a2 |, ,| an |]2 3．设 an x n an 1 x n 1 a1 x a0 （1）
a bq1 r1 , b r1q2 r2 , , rn 2 rn 1qn rn , rn 1 rn qn 1 , 0 rn 1 rn rn 1 r1 b
(a, b) rn d | a bq1 r1 ， d | b r1q2 r2 ，┄, d | rn 2 rn 1qn rn (a, b) ,
充分性。若存在整数 s，t 使 as+bt=1，则 a，b 不全为 0。 又因为 ( a, b) | a, ( a, b) | b ，所以 ( a, b | as bt ) 又 ( a, b) 0 ， ( a, b) 1 2．证明定理 3 定理 3 即 ( a, b) |1 。
a1 , a2 , an | a1 |,| a2 | ,| an |
且 | tn |
|t | b , , 如此类推知： 2 22
| tn 1 | | tn 2 | |t | |b| 2 n n 1 2 2 2 2
而 b 是一个有限数，n N , 使 tn 1 0
(a, b) (b, t ) (t , t1 ) (t1 , t2 ) (tn , tn 1 ) (tn , 0) tn ，存在其求法为： (a, b) (b, a bs ) (a bs, b (a bs ) s1 )
证：由 P3§1 习题 4 知在（1）式中有
0 rn 1 rn 1
rn 1 rn 2 r b 2 n11 n ，而 rn1 2 2 2 2
b , 2n b ， 2n
n log 2 b
log b log b ，即 n log 2 log 2
即存在一个整数 q ，使
(i ) 当 q 为偶数时，若 b 0. 则令 s
b q q q 0 a bs t a b a b b t 2 2 2 2
若 b 0 则令 s
b q q , t a bs a b ，则同样有 t 2 2 2
即 q1a1 q2 a2 qn an 是 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)
3．若 ax0 by0 是形如 ax by （x，y 是任意整数，a，b 是两不全为零的整数）的数中最小 整数，则 (ax0 by0 ) | (ax by ) ．
1 / 78
《初等数论》 （闵嗣鹤、严士健编著） （第三版）习题解答
证： a, b 不全为 0
在整数集合 S ax by | x, y Z 中存在正整数，因而有形如 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 使得
p p p an ( ) n an 1 ( ) n 1 a1 a0 0 q q q
an p n an 1 p n 1q a1 pq n 1 a0 q n 0
由 (2) an p n an 1 p n 1q a1 pq n 1 a0 q n ， 所以 q 整除上式的右端，所以 q | an p n ，又 ( p, q ) 1, q 1 ， 所以 ( q, p n ) 1, q | an ； 又由（2）有 an p n an 1 p n 1q a1 pq n 1 a0 q n 因为 p 整除上式的右端，所以 P | a0 q n ， ( p, q ) 1, q 1 ，所以 ( q n , p ) 1, 故（1）的有理根为 （2）