- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
带余除法的应用举例
例1
而
证明形如3n-1的数不是平方数。
a 3q r , 3k r 2 3n 1, 0 r 3， 0 r 3. (3q r ) 2 9q 2 6qr r 2 3(q 2 6qr) r 2
证明：a Z ,
(分别考虑r 0,1, 2的情形)
则有 a2
k i
1，取d k i a 1，则d 就满足要求。
$2
1、定义
最大公因数与辗转相除法
设a1 , a2 , , an是n(n 2)个整数，若整数d 是
它们之中每一个的因数，那么d就叫作a1 , a2 , , an的一个 公因数。所有公因数中最大的一个叫最大公因数，记作 （a1 , a2 , , an），若（a1 , a2 , , an） =1，则说a1 , a2 , , an互质 或互素。
(ii )若在r1 , , r5中数0， 1，至少有一个不出现， 2 这样至少有3个ri要取相同的值，不妨设 r1 r2 r3 r(r 0,1或2）， a1 a2 a3 3(q1 q2 q3 ) 3r 可以被3整除。 此时
例3、设a 1为奇数，证明： 存在正整数d a 1,Fra Baidu bibliotek使得a 2 1
a(qk qi ) 2k 2i 2i (2k i 1)
因而a个余数r0 , r1 , , ra 1仅可能取a 1个值， 因此其中必有两个相等。
设为ri，rk，不妨设0 i k a，因而有 a(qk qi ) 2k 2i 2i (2k i 1)
如果不存在整数q使得a bq成立，则称a不被b整除， 记为b † a。
2、整除的基本定理
定理1（传递性）：ab，bc ac 定理2：若a，b都是m的倍数，则ab都是m的倍数
定理3： 若a1 , a2 ,, an都是m的倍数，q1 , q2 ,, qn 是任意n个整数，则a1q1 a2 q2 an qn是m的倍数
证明分析：作序列 b 2b 3b ，,,- ,0, , , , 2 2 2 2 2 2 b b 则a必满足q a<(q+1) , 其中q Z , 2 2 分q为偶数时b 0和b 0；q为偶数时b 0和 b 0来讨论q及r的存在性, 进一步证明q, r的唯一性。 3b 2b b
带余数除法的第三种表示 定理4： 若a, b是两个整数，其中b 0，则存在着两个整数 q及r，使得 b a bq r， r 2 成立，而且当b是奇数时，q及r是唯一的；当b是偶数时，q及r 有可能是不唯一的。
例
当a 5,
b 2时，可有
5 （ 2） （ 3 ） （ 1 ），即q 3, r 1; 或5 （ 2） （ 2） 1 ，即q 2, r 1
d
证：考虑下面的a个数： 2 , 2 ,, 2 ，显然a不整除2 (0 j a)，
0 1 j a 1
由带余除法，对每个2 (0 j a)，
j
2 j q j a rj , (0 rj a )
因而a个余数r0 , r1 , , ra 1仅可能取a 1个值， 因此其中必有两个相等。 设为ri，rk，不妨设0 i k a，因而有
带余数除法的第二种表示 定理4： 若a, b是两个整数，其中b 0，则存在着两个整数 q及r，使得 a bq r， 成立，而且q及r是唯一的。 0r b
证明分析：作整数序列 ，-3 b ,-2 b ,- b ,0,b ,2 b ,3 b , 则a必满足q b a<(q+1) b , 其中q Z , 令a q b r可得到a b q r , 分b 0和 b 0来讨论q, 进一步证明q, r的唯一性。
2、任意整数的最大公因数可转化为正整数来讨论
定理1
若a1 , a2 , , an是任意n个不全为零的整数，
则 （i ) a1 , a2 , , an 与 a1 , a2 ,, an 的公因数相同； (ii)(a1 , a2 , , an ) ( a1 , a2 ,, an ).
3、下面先讨论两个非负整数的最大公因数 定理2 设b是任一正整数，则 (i)0与b的公因数就是b的因数，反之， b的因数也 就是0与b的公因数。 (ii) (0,b)=b。
第一章 整数的因子分解
University
of
Science
and
Technology
of
China
第一章 整数的因子分解
•整除的概念 带余数除法
•最大公因数与辗转相除法 •整除的进一步性质
•质数（素数） 算术基本定理
•取整函数及其在数论中的一个应用
$1 整除的概念 带余数除法
定义 设a, b是任意两个整数，其中b 0，如果 存在一个整数q使得等式 a qb 成立，就说b整除a或a被b整除，记作b a， 此时把b 叫作a的因数，把a叫作b的倍数.
例2、任意给出的5个整数中，必有3个数之 和被3整除。
证：设这5个数为ai , i 1,,5，记 ai 3qi ri， 0 ri 3, i 1,,5。 分别考虑以下两种情形：
(i)若在r1 , , r5中数0， 1， 2都出现，不妨设 r1 0, r2 1, r3 2， a1 a2 a3 3(q1 q2 q3 ) 3 可以被3整除。 此时
3、带余数除法
定理4： 若a, b是两个整数，其中b 0，则存在着两个整数 q及r，使得 a bq r， 成立，而且q及r是唯一的。 ()式中的q及r分别叫a被b除所得的商和余数。 0r b ()
证明分析：作整数序列 ，-3b,-2b,-b,0,b,2b,3b, 则a必满足qb a<(q+1)b, 的唯一性。 其中q Z , 令a qb r可得到a bq r , 进一步证明q, r
