14
二、辗转相除法
在a b 的带余数除法中， 定义：设有整数 a , b(b 0)，
每次用余数去除除数，直到余数为0停止，这种运算 方法称为辗转相除法。即有
a b q1 (余r1 ) a bq1 r1 , 0 r1 b
b r1 q2 (余r2 ) b r1q2 r2 , 0 r2 r1 或 ( * ) rn 2 rn1qn rn , 0 rn rn1 rn 2 rn1 qn (余rn ) rn1 rn qn1 ,( rn1 0) rn1 rnqn1 rn1 , rn1 0.
8
例6 已知： 782 + 8161能被57整除， 求证：783 +8163也能被57整除。 证明：783 + 8163 = 7 ( 782 + 8161 )－7 × 8161 + 8163 = 7 ( 782 + 8161 ) + 8161 × 57 ∵782 + 8161和57都能被57整除 ∴原式得证。
(1) (a1 , a2 , , an ) ( a1 , a2 , , an ); (2) b a (a , b ) b ; (0, b ) b ;
(3) a bq r , q 0 (a , b ) (b, r ).
注：定理1(3)给出了求最大公因数的方法 ——辗转相除法.
20
定理6 设(a1 , a2 ) d 2 ,(d 2 , a3 ) d 3 , ,(d n1 , an ) d n ，
则 (a1 , a2 , , an ) d n . 证明：设(a1 , a2 , , an ) d， 一方面，d a1 , d a2 d d 2 d d n ； 另一方面， (d n1 , an ) d n d n an , d n d n1 d n a1 d n d . 所以，d n d .
12
§1.2 最大公因数与辗转相除法
一、最大公因数
定义：若 d a1 ,, d an (n 2), 则称d是a1 , a2 ,, an的一个 公因数，其中最大的称为最大公因数，记作(a1 , a2 ,, an ). 若(a1 , a2 , , an )，则称a1 , a2 , , an互质(素)； 其中每两个都互质，则称a1 , a2 , , an两两互质. 注：a1 , a2 , , an两两互质 a1 , a2 , , an互质.
令 r a qb ， 则有 a bq r , 0 r b 成立. a bq r , 0 r b
唯一性：反证〔略〕
5
例3 利用带余数除法，由a, b的值求q, r .
(1) a 14, b 3 (2) a 14, b 3 (3)a 14, b 3 14 3 4 ( 余 2 ), q 4, r 2 14 3 5 ( 余 1 ), q 5, r 1 14 ( 3) 14 3
由带余除法有 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 )即是a , b的最大公约数.
相关概念：因数、约数、倍数、奇数、偶数。 注：显然每个非零整数a都有约数 1，a，称这四个 数为a的平凡约数，a的另外的约数称为非平凡约数。 例1 有一个自然数乘以9后，得到一个仅由数字1组成 的多位数，求这个自然数最小为多少？ 12345679 b a , c b c a 定理2
例1 已知两个自然数的和为165，它们的最大公约数 为15，求这两个数。 15与150，或30与135，或45与120， 或60与105，或75与90.
13
练习：100个正整数之和为101101，则它们的最大 公约数的最大可能值是多少?证明你的结论。 1001 若这100个数互不相同呢？ 定理1-3：〔有关最大公因数的结论〕
10
q q q为偶数，且b 0时，令s , t a bs a b 2 2 b 同样有 t . 2 q1 q1 (2)当q为奇数且b 0时，令s , t a bs a b 2 2 b b q1 则 t a bs a b 0， t 2 2 2 q1 q1 若b 0, 令 s , t a bs a b 2 2 b 同样有 t . 存在性得证 ；下证唯一性. 2
1859 1573 5 286 286 0
1573 1 1430 143 2
注：亦可通过分解因数的方法求最大公因数.
18
补充说明：利用§1.1习题4的结论，可以使得辗转 相除法求最大公因数更为快速一些。每次除得余数 的绝对值不超过除数的一半，余数可以为负。 例3 求（76501，9719）=1. 76501 77752 8 1251 1156 3 95 96 4 1 9719 8 10008 289 4 285 4 24 4 0
第一章 整数的可除性
整除性理论是初等数论的基础，本章要介绍 带余数除法，辗转相除法，最大公约数，最小公 倍数， 函数 x、 x 的性质，算术基本定理以及 它们的一些应用。
1
§1.1 一、整除的概念
整除的概念
带余数除法
定义1：设a , b是整数，b 0, 如果存在整数q , 使得 a bq成立，则称b整除a , 或a能被b整除.记作：b a .
证明：先考虑两个数的情形， 一方面，(a1 , a2 )的因数显然是a1 , a2的公因数. 另一方面，由辗转相除法可以得到，
a1 , a2的公因数一定是rn的因数. 所以， (a1 , a2 )的因数与a1 , a2的公因数完全相同.
对于多个整数的公因数，利用
(a1 , a2 , , an ) ((a1 , a2 ,), an )
当b为偶数时,s, t可以不唯一，举例如下：
令 b 6, t 3, t1 3, s 5 a bs t 33; a t1 33 3 s1 6. b 6 显然有 33 6 5 3 6 6 3， 即s , t不唯一。
注：该例为简化辗转相除法求最大公约数提供了依据。
3
三、带余数除法 定理4 设a与b是两个整数，b > 0，则存在唯一 的两个整数q和r，使得
a bq r , 0 r b (1)
定义2：（1）式通常写成
a b q (余 r ) (2)
并称q为a被b除所得的不完全商； r叫做a被b除所得的余数； (2)式称为带余数除法。
4
定理4 设a与b是两个整数，b > 0，则存在唯一 的两个整数q和r，使得 证明： 存在性：考虑整数序列 , 3b, 2b, b,0, b,2b,3b, 则a必在序列的某两项之间， 即存在一个整数q，使得 qb a (q 1)b
注：一般地，要求a , q是整数，b, r是非负整数；
如果允许b取负值，则要求 0 r b . 思考 28 6 14 3 4 (余 2) 正确吗？
6
例4. 若ax0 by0是形如ax by(a , b, x , y Z , a , b不全为0) 的最小正整数，则有(ax0 by0 ) (ax by ). a , b不全为0， 证明： 在S ax by | x , y Z 中存在正整数， 所以，存在形如ax by的最小正整数ax0 by0 .
P28
7
例5 设n为整数，求证：24∣n(n+2)(5n+1)(5n－1). 证明：f ( n ) = n ( n + 2 ) ( 5n + 1 ) ( 5n－1 ) = n ( n + 2 ) [ ( n2－1) + 24n2] = ( n－1 ) n ( n + 1 ) ( n + 2 ) + 24 n3 ( n + 2 ) ∵4!∣( n－1) n ( n + 1 ) ( n + 2 ), 24∣24 n3 ( n + 2 ) ∴24∣f ( n ). 练习：对于任意的五个自然数,证明其中必有3 个数的和能被3整除。
可以证明.
17
例2 求下面各组数的最大公因数。
(1) a 1859, b 1573; (2) a 138, b 36.
解： 1859 1573 1 286;
1573 286 5143; 286 143 2 0. 所以， ( 1859, b 1573) 143. (2) (138, 36) 6.
m a , m b m (a b)
定理3 m a1 , , m an , q1 , , qn Z m (q1a1 qnan ) 例2 (1) 已知：x和y是整数，13︱( 9x + 10y )， 求证：13︱( 4x + 3y )； (2)若 a ,b 是整数，且7∣( a + b ), 7∣( 2a－b )， 证明:7|( 5a + 2b )。
19
定理5 设a , b不全为0, m 0, 则有：
(1) (am , bm ) m (a , b ); a b (a , b) (2) 若d a , d b , 则 ( , ) ； d d d a b 特别地，( , ) 1. (a , b) (a , b)
说明： （1）在 ( * )式中，所有各项都乘以m可以得证。 （2）由(1)即可得证。
由rn1 qn1rn rn rn1 rn b , rn a , 另一方面， (a , b) rn , ( rn1 0). 即rn是a , b的一个公因数. 所以，