2018/10/7
阜阳师范学院 数科院
10
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
所以，存在形如ax by的最小正整数ax0 by0 .
由带余除法有 ax by (ax0 by0 )q r ,0 r ax0 by0
显然，r ( x x0q)a ( y y0q )b S， 由ax0 by0是S中的最小正整数，知 r 0.
被57整除。
2018/10/7
阜阳师范学院 数科院
1
5.设n为整数，求证:24∣n(n+2)(5n+1)(5n－1). 6. 100个正整数之和为101101，则它们的最大公约
数的最大可能值是多少?证明你的结论。
1 1 1 7. 证明T 1 ( n 1)不是整数. 2 3 n
2018/10/7
(2)
阜阳师范学院 数科院
5
定理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
rn1 rn qn1 ,( rn1 0)
2018/10/7
rn1 rnqn1 rn1 ,
rn1 0.
阜阳师范学院 数科院
17
定理2 在上面的表达式( * )中，有 (a , b) rn , (rn1 0). 证明：令 (a , b) d , 则 d a , d b .
8. 求自然数n，使得2 2 2 是一个整数的平方。
8 11 n
2018/10/7
阜阳师范学院 数科院
2
§1.1 一、整除的概念
整除的概念
带余数除法
定义1：设a , b是整数，b 0, 如果存在整数q, 使得
a bq成立，则称b整除a , 或a能被b整除.记作：b a .
相关概念：因数、约数、倍数、奇数、偶数。 注：显然每个非零整数a都有约数 1，a，称这四个 数为a的平凡约数，a的另外的约数称为非平凡约数。 例1 有一个自然数乘以9后，得到一个仅由数字1组成 的多位数，求这个自然数最小为多少？ 12345679
2018/10/7
可以证明.
19
阜阳师范学院 数科院
例2 求下面各组数的最大公因数。
(1) a 1859, b 1573; (2) a 138, b 36.
解： 1859 1573 1286;
1573 286 5143; 286 143 2 0.
1859 1573 5 286 286 0
1001
(3) a bq r , q 0 (a , b) (b, r ).
注：定理1(3)给出了求最大公因数的方法
——辗转相除法.
2018/10/7
阜阳师范学院 数科院
16
二、辗转相除法
在 a b 的带余数除法中， 定义：设有整数 a , b(b 0)，
每次用余数去除除数，直到余数为0停止，这种运算 方法称为辗转相除法。即有
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不唯一。
注：该例为简化辗转相除法求最大公约数提13
2018/10/7
阜阳师范学院 数科院
14
§1.2 最大公因数与辗转相除法
一、最大公因数
定义：若 d a1 , , d an ( n 2), 则称d 是a1 , a2 , , an的一个
公因数，其中最大的称为最大公因数，记作(a1 , a2 ,, an ). 若(a1 , a2 ,, an )，则称a1 , a2 ,, an互质(素)；
即有 (ax0 by0 ) (ax by ).
注： (ax0 by0 )即是a , b的最大公约数.
2018/10/7
阜阳师范学院 数科院
8
例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整除。
阜阳师范学院 数科院
15
练习：100个正整数之和为101101，则它们的最大
公约数的最大可能值是多少?证明你的结论。
若这100个数互不相同呢？ 定理1：〔有关最大公因数的结论〕
(1) (a1 , a2 , , an ) ( a1 , a2 , , an ); (2) b a (a , b ) b ; (0, b ) b ;
7
2018/10/7
阜阳师范学院 数科院
例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 中存在正整数，
14 3 4 ( 余 2 ), q 4, r 2 14 3 5 ( 余 1 ), q 5, r 1
14 ( 3) 14 3
注：一般地，要求a, q是整数，b, r是非负整数；
如果允许b取负值，则要求 0 r b . 思考 28 6 14 3 4 (余 2) 正确吗？
中小学数学中的一些数论问题： 1.狐狸在跑道上跳远，每次跳远150CM从起点开始每
隔130CM设一个陷阱，问狐狸跳了几次后掉进井中？
2.已知66︱X1998Y，求所有满足条件的六位数X1998Y.
3.有一个自然数乘以9后，得到一个仅由数字1组成
的多位数，求这个自然数最小为多少？ 4.已知: 782 + 8161能被57整除，求证：783 +8163也能
证明：先考虑两个数的情形， 一方面，(a1 , a2 )的因数显然是a1 , a2的公因数. 另一方面，由辗转相除法可以得到，
a1 , a2的公因数一定是rn的因数.
所以， (a1 , a2 )的因数与a1 , a2的公因数完全相同.
对于多个整数的公因数，利用
(a1 , a2 ,, an ) ((a1 , a2 ,), an )
1573 1 1430 143 2
所以， ( 1859, b 1573) 143.
由rn1 qn1rn rn rn1 rn b , rn a , 另一方面，
(a, b) rn , (rn1 0). 即rn是a, b的一个公因数. 所以，
2018/10/7
阜阳师范学院 数科院
18
定理3 a1 , a2 ,, an的公因数与(a1 , a2 ,, an )的因数相同.
其中每两个都互质，则称a1 , a2 ,, an两两互质.
注：a1 , a2 ,, an两两互质 a1 , a2 ,, an互质. 例1 已知两个自然数的和为165，它们的最大公约数
为15，求这两个数。
15与150，或30与135，或45与120， 或60与105，或75与90.
2018/10/7
2018/10/7
q q1 又 b a b， 2 2
阜阳师范学院 数科院
12
设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)
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 .
令 r a qb ， 则有 a bq r , 0 r b 成立.
唯一性：反证〔略〕
2018/10/7
阜阳师范学院 数科院
6
例3 利用带余数除法，由a, b的值求q, r .
(1) a 14, b 3 (2) a 14, b 3 (3)a 14, b 3
2018/10/7
阜阳师范学院 数科院
11
q q q为偶数，且b 0时，令s , t a bs a b 2 2