§2初等数论--整除

由rn1 qn1rn rn rn1 rn b , rn a , 另一方面，
(a, b) rn , (rn1 0). 即rn是a, b的一个公因数. 所以，
2017/3/22
阜阳师范学院 数科院
20
定理3 a1 , a2 ,, an的公因数与(a1 , a2 ,, an )的因数相同.
s s1 , t t1 . 当b为奇数时，②式中的等号不能成立，
当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不唯一。
阜阳师范学院 数科院
17
练习：100个正整数之和为101101，则它们的最大
公约数的最大可能值是多少?证明你的结论。
若这100个数互不相同呢？ 定理1：〔有关最大公因数的结论〕
(1) (a1 , a2 , , an ) ( a1 , a2 , , an ); (2) b a (a , b ) b ; (0, b ) b ;
2017/3/22
6
三、带余数除法 定理4 设a与b是两个整数，b > 0，则存在唯一
的两个整数q和r，使得
a bq r , 0 r b (1)
定义2：（1）式通常写成
a b q (余r )
并称q为a被b除所得的不完全商； r叫做a被b除所得的余数； (2)式称为带余数除法。
令 r a qb ， 则有 a bq r , 0 r b 成立.
唯一性：反证〔略〕
2017/3/22
8
例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
证明：先考虑两个数的情形， 一方面，(a1 , a2 )的因数显然是a1 , a2的公因数. 另一方面，由辗转相除法可以得到，
a1 , a2的公因数一定是rn的因数.
所以， (a1 , a2 )的因数与a1 , a2的公因数完全相同.
对于多个整数的公因数，利用
(a1 , a2 ,, an ) ((a1 , a2 ,), an )
a bq成立，则称b整除a , 或a能被b整除.记作：b a .
相关概念：因数、约数、倍数、奇数、偶数。 注：显然每个非零整数a都有约数 1，a，称这四个 数为a的平凡约数，a的另外的约数称为非平凡约数。 例1 有一个自然数乘以9后，得到一个仅由数字1组成 的多位数，求这个自然数最小为多少？ 12345679
a bq1 r1 b r1q2 r2 rn 2 rn1qn rn rn1 rnqn1 rn1
由r1 a bq1 d r1 ; 由r2 b r1q2 d r2 ;

由rn rn 2 rn1qn d rn .
第一章 整数的可除性
整除性理论是初等数论的基础，本章要介绍 带余数除法，辗转相除法，最大公约数，最小公 倍数， 函数 x、 x 的性质，算术基本定理以及 它们的一些应用。
2017/3/22
阜阳师范学院 数科院
2
中小学数学中的一些数论问题：
1.设n为整数，求证:24∣n(n+2)(5n+1)(5n－1).
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 rn2 rn1 qn (余rn )
1001
(3) a bq r , q 0 (a , b) (b, r ).
注：定理1(3)给出了求最大公因数的方法
——辗转相除法.
2017/3/22
阜阳师范学院 数科院
18
二、辗转相除法
在a b 的带余数除法中， 定义：设有整数 a , b(b 0)，
每次用余数去除除数，直到余数为0停止，这种运算 方法称为辗转相除法。即有
数论是竞赛数学中最重要的一部分，特别是在1991 年，IMO在中国举行，国际上戏称那一年为数论年，因为6 道IMO试题中有5道与数论有关。 数论的魅力在于它可以适合小孩到老头，只要有算术 基础的人均可以研究数论――在前几年还盛传广东的一位 农民数学爱好者证明了哥德巴赫猜想，当然，这一谣言最 终被澄清了。可是这也说明了最难的数论问题，适合于任 何人去研究。 初等数论最基础的理论在于整除，由它可以演化出许 多数论定理。
显然，r ( x x0q)a ( y y0q)b S， 由ax0 by0是S中的最小正整数，知 r 0.
即有 (ax0 by0 ) (ax by ).
注： (ax0 by0 )即是a , b的最大公约数.
2017/3/22
10
例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整除。
注：该例为简化辗转相除法求最大公约数提供了依据。
2017/3/22
阜阳师范学院 数科院
15
2017/3/22
阜阳师范学院 数科院
16
§1.2 最大公因数与辗转相除法
一、最大公因数
定义：若 d a1 , , d an ( n 2), 则称d 是a1 , a2 , , an的一个
公因数，其中最大的称为最大公因数，记作(a1 , a2 ,, an ). 若(a1 , a2 ,, an )，则称a1 , a2 ,, an互质(素)；
2017/3/22
阜阳师范学院 数科院
13
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
2017/3/22
阜阳师范学院 数科院
12
b 0, 设a, b是任意两个整数， b 证明：存在两个整数s, t，使得 a bs t , t . 2 并且，当b为奇数时，s, t是唯一的。b为偶数呢？
习题选讲 P4－4
3b 2b b b 2b 3b 证：作序列, , , ,0, , , , 2 2 2 2 2 2 则a必在此序列的某两项之间， q q1 即 q Z , 使得 b a b. 2 2 q q (1)q为偶数，且b 0时，令s , t a bs a b 2 2 b q q 1 则有 0 a bs t a b a b b t . 2 2 2 2
rn1 rn qn1 ,( rn1 0)
2017/3/22
rn1 rnqn1 rn1 ,
rn1 0.
阜阳师范学院 数科院
19
定理2 在上面的表达式( * )中，有 (a , b) rn , (rn1 0). 证明：令 (a , b) d , 则 d a , d b .
2.已知66︱X1998Y，求所有满足条件的六位数X1998Y.
3.有一个自然数乘以9后，得到一个仅由数字1组成
的多位数，求这个自然数最小为多少？ 4.已知: 782 + 8161能被57整除，求证：783 +8163也能
被57整除。
2017/3/22
阜阳师范学院 数科院
3
5. 100个正整数之和为101101，则它们的最大公约
数的最大可能值是多少?证明你的结论。
1 1 1 6. 证明T 1 ( n 1)不是整数. 2 3 n
7. 求自然数n，使得2 2 2 是一个整数的平方。
8 11 n
2017/3/22
4
§1.1 一、整除的概念
整除的概念
带余数除法
定义1：设a , b是整数，b 0, 如果存在整数q, 使得
2017/3/22
5
二、整除的性质 定理1〔传递性〕 b a , c b c a 定理2
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 )。
其中每两个都互质，则称a1 , a2 ,, an两两互质.
注：a1 , a2 ,, an两两互质 a1 , a2 ,, an互质. 例1 已知两个自然数的和为165，它们的最大公约数
为15，求这两个数。
15与150，或30与135，或45与120， 或60与105，或75与90.
2017/3/22
2017/3/22
ቤተ መጻሕፍቲ ባይዱ
(2)
7
定理4 设a与b是两个整数，b > 0，则存在唯一
的两个整数q和r，使得 证明： 存在性：考虑整数序列 , 3b, 2b, b,0, b,2b,3b, 则a必在序列的某两项之间(包括这两项）， 即存在一个整数q，使得 qb a (q 1)b
a bq r , 0 r b
2017/3/22
q q1 又 b a b， 2 2
阜阳师范学院 数科院
14
设a bs t bs1 t1，s1 s, 则 t t1 b( s1 s ) b ，(1)
b b 另一方面， t , t1 2 2
t t1 t t 1 b (2)
2017/3/22
阜阳师范学院 数科院
11
例6 已知： 782 + 8161能被57整除， 求证：783 +8163也能被57整除。 证明：783 + 8163 = 7 ( 782 + 8161 )－7 × 8161 + 8163 = 7 ( 782 + 8161 ) + 8161 × 57 ∵782 + 8161和57都能被57整除 ∴原式得证。
的最小正整数，则有(ax0 by0 ) (ax by ).
a , b不全为0， 证明：
在S ax by | x , y Z 中存在正整数，
所以，存在形如ax by的最小正整数ax0 by0 .
由带余除法有 ax by (ax0 by0 )q r ,0 r ax0 by0
14 ( 3) 14 3
注：一般地，要求a, q是整数，b, r是非负整数；
如果允许b取负值，则要求 0 r b . 思考 28 6 14 3 4 (余 2) 正确吗？
9
2017/3/22
例4. 若ax0 by0是形如ax by(a, b, x, y Z , a, b不全为0)