《初等数论：数的整除性资料》由会员分享，可在线阅读，更多相关《初等数论：数的整除性资料（32页珍藏版）》请在金锄头文库上搜索。
1、初等数论初等数论 第一章第一章 整数的可除性整数的可除性 1 第一章第一章 整除理论整除理论 整除性理论是初等数论的基础整除性理论是初等数论的基础。 本章要介绍本章要介绍带余数除法带余数除法，辗转相除法辗转相除法，最大公约数最大公约数， 最小公倍数最小公倍数，算术基本定理算术基本定理以及它们的一些应用以及它们的一些应用。 初等数论初等数论 第一章第一章 整数的可除性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 2 第一节第一节 1 1 数的整除性数的整除性 定义定义 1. 1. 设设a a，b b是整数是整数，b b 0 0，如果存在整数如果存在整数q q， 使得使得a a = =
2、 b bq q成立成立，则称则称a a被被b b整除整除， a a是是b b的的倍数倍数，b b是是a a的的约数约数（因数或除数因数或除数） ，） ， 并且使用记号并且使用记号b b a a； 如果不存在整数如果不存在整数q q使得使得a a = = b bq q成立成立， 则称则称a a不被不被b b整除整除， 记为记为b b | a a。 初等数论初等数论 第一章第一章 整数的可除性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 3 显然每个非零整数显然每个非零整数a a都有约数都有约数 1 1， a a， 称这四个数为称这四个数为a a的的平凡约平凡约数数， a a的另外的约
3、数称为的另外的约数称为非平凡约数非平凡约数。 被被 2 2 整除的整数称为整除的整数称为偶数偶数， 不被不被 2 2 整除的整数称为整除的整数称为奇数奇数。 初等数论初等数论 第一章第一章 整数的可除性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 4 定理定理 1.1. 下面的结论成立下面的结论成立： ( () ) a a b b a a b b； 证明证明：因为因为a a b b，故故b b = = a aq q，即即 b b = = a aq q，故故 a a b b。 ( () ) a a b b，b b c c a a c c； （传递性传递性） 证明证明：因因a a b
4、b，b b c c，故故b b = = a aq q1 1，c=bqc=bq2 2， 则则c=c=a aq q1 1q q2 2，故故a a c c。 ( () ) b b a ai i， （i i = = 1 1, , 2 2, , , , k k ） b b a a1 1x x1 1 a a2 2x x2 2 a ak kx xk k， 初等数论初等数论 第一章第一章 整数的可除性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 5 此处此处x xi i（i i = = 1 1, , 2 2, , , , k k）是任意的整数是任意的整数； 证明证明：因为因为b b a ai i，
5、 （i i = = 1 1, , 2 2, , , , k k ） ，） ，所以所以 a ai i=bq=bqi i, , a ai ix xi i=bq=bqi ix xi i（i i = = 1 1, , 2 2, , , , k k ） 故故a a1 1x x1 1 a a2 2x x2 2 a ak kx xk k= =b(qb(q1 1x x1 1 q q2 2x x2 2 q qk kx xk k) ) 因此因此b b a a1 1x x1 1 a a2 2x x2 2 a ak kx xk k， 此处此处x xi i（i i = = 1 1, , 2 2, , , , k k）是
6、任意的整数是任意的整数 ( () ) b b a a bcbc acac，此处此处c c是任意的非零整数是任意的非零整数； 初等数论初等数论 第一章第一章 整数的可除性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 6 证明证明：因因b b a a ，故故a a = = b bq q，即即 ac=bcq,ac=bcq,则则bcbc acac， 此处此处c c是任意的非零整数是任意的非零整数。 ( () ) b b a a，a a 0 0 | |b b| | | |a a| |； 证明证明：因因b b a a，故故a a = = b bq q，即即| |a a| |= =| |b b|
7、q q| |，又因又因 a a 0 0， 则则q q 0 0，故故| |q q| | 1 1，故故 | |b b| | |a a| |； ( () ) b b a a且且| |a a| 1 1，e e2 2 1 1，使得使得d d1 1 = = e e1 1e e2 2， 因此因此，e e1 1和和e e2 2也是也是a a的正的非平凡约数的正的非平凡约数。 这与这与d d1 1的最小性矛盾的最小性矛盾。所以所以d d1 1是素数是素数。证毕证毕。 初等数论初等数论 第一章第一章 整数的可除性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 9 推论推论. . 任何大于任何大于 1 1
8、 的合数的合数a a必有一个不超过必有一个不超过 a的素约数 的素约数。 证明证明：使用定理使用定理 2 2 中的记中的记号号，有有a a = = d d1 1d d2 2， 其中其中d d1 1 1 1 是最小的素约数是最小的素约数， 所以所以d d1 1 2 2 a a。 。证毕证毕。 初等数论初等数论 第一章第一章 整数的可除性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 10 例例 1.1. 设设r r是正奇数是正奇数，证明证明：对任意的正整数对任意的正整数n n，有有 n n 2 2 | 1 1 r r 2 2 r r n n r r。 。 解解： 对于任意的正整数对于任
9、意的正整数a a，b b以及正奇数以及正奇数k k，有有 a a k k b bk k = = ( (a a b b)( )(a a k k 1 1 a ak k 2 2b b a ak k 3 3b b2 2 b b k k 1 1) ) = = ( (a a b b) )q q，其中其中q q是整数是整数。 记记s s = = 1 1 r r 2 2 r r n n r r， ， 则则 2 2s s = = 2 2 (2(2 r r n n r r) ) (3 (3 r r ( (n n 1) 1) r r) ) ( (n n r r 2 2 r r) ) = = 2 2 ( (n n 2
10、) 2)Q Q，其中其中Q Q是整数是整数。 若若n n 2 2 s s，由上式知由上式知n n 2 2 2 2， 因为因为n n 2 2 2 2，这是不可能的这是不可能的，所以所以n n 2 2 | s s。 初等数论初等数论 第一章第一章 整数的可除性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 11 例例 2 2. . 设设A A = = d d1 1, , d d2 2, , , , d dk k 是是n n的所有约数的集合的所有约数的集合， 则则B B = = , 21k d n d n d n 也是也是n n的所有约数的集合的所有约数的集合。 解解： 由以下三点理由可以
11、证得结论由以下三点理由可以证得结论： ( () ) A A和和B B的元的元素个数相同素个数相同； ( () ) 若若d di i A A，即即d di i n n，则则 | i d n n n，反之亦然反之亦然； ( () ) 若若d di i d dj j，则则 ji d n d n 。 初等数论初等数论 第一章第一章 整数的可除性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 12 例例 3 3. . 以以d d( (n n) )表示表示n n的正约数的个数的正约数的个数， 例如例如：d d(1)(1) = = 1 1，d d(2)(2) = = 2 2，d d(3)(3) =
12、 = 2 2，d d(4)(4) = = 3 3， 。 问问：d d(1)(1) d d(2)(2) d d(1997)(1997)是否为偶数是否为偶数？ 解解： 对于对于n n的每个约数的每个约数d d，都有都有n n = = d d d n ，因此因此，n n的正的正 约数约数d d与与 d n 是成对地出现的是成对地出现的。只有当只有当d d = = d n ，即即n n = = d d 2 2 时时， d d和和 d n 才是同一个数才是同一个数。 故当且仅当故当且仅当n n是完全平方数时是完全平方数时，d d( (n n) )是奇数是奇数。 初等数论初等数论 第一章第一章 整数的可除
13、性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 13 因为因为 4444 2 2 1 1， 证明证明：若若p p 3 n， ，则则n n1 1是素数是素数。 5. 5. 证明证明：存在无穷多个自然数存在无穷多个自然数n n，使得使得n n不能表示不能表示为为 a a 2 2 p p （a a 0 0 是整数是整数，p p为素数为素数）的形式的形式。 初等数论初等数论 第一章第一章 整数的可除性整数的可除性 第一节第一节 1 1 数的整除性数的整除性 29 习题一习题一 1 1 答案答案 1. 1. ( () ) 由由a a b b知知b b = = aqaq， 于是于是b b = ( = ( a a) )( ( q q) )， b b = = a a( ( q q) )及及 b b = ( = ( a a) )q q， 即即 a a b b，a a b b及及 a a b b。 反之反之，由由 a a b b，a a b b及及 a a b b也可得也可得a a b b； ( () ) 由由a a b b，b b c c知知b b = = aqaq1 1，c c = = bqbq2 2， 于是于是c c = = a
