初等数论整数的可除性

1、第一章整数的可除性§ 1整除整数集对于加、减、乘三种运算都是封闭的，但是对于除法运算不封闭。为此，我们引进整除的概念。定义1设a, bCZ, bw0,如果存在qCZ,使得等式a=bq成立，那么称b 整除a或a被b整除，记作：b| a,此时称b为a的因数(约数)，a为b的倍 数。如果不存在满足等式 a=bq的整数q,那么称b不能整除a或a不被b整除， 记作b | a。定理 1 设 a, b, cCZ, bw0, cw0,则(1)如果 c| b, b|a,那么 c| a；(2)如果b|a,那么bc| ac;反之亦真；(3)如果c| a, c| b,那么，对于任意 mnCZ,有c|( ma

2、mb)；(4)如果 b| a, aw。，那么 |b | w | a| ；(5)如果 b| a, a| b,那么 | b|=| a|。证明可选证。定理2 (带余除法)设a, bCZ, bw0,则存在q, rCZ,使得a=bq+r, 0< r<| b| ,并且q及r是唯一的。证明 当b|a时，取q=a/ b, r=0即可。当b!| a时，考虑集合 E=a-bk|kCZ ,易知E中有正整数，因此 E中有 最小正整数，设为r=a-bk>0,下证：r <| b|。因为b!| a,所以r * | b| ,若r >| b| , 则r =r-|b|>0，又r YE,故与r的

3、最小性矛盾，从而存在q, r Z,使得a=bq+r,0< r<| b| 。精选资料，欢迎下载唯一性。设另有 q',r'CZ,使得 a=bq'+r', 0wr'<|b|,则 b( q-q')= r'-r , 于是 b|( r '-r),但由于 0w | r '-r |<| b| ,故 r '-r =0,即 r=r 从而 q=q'。定义2等式a=bq+r, 0< r <| b|中的整数q称为a被b除所得的(不完全) 商，整数r称为a被b除所得的余数。注r=0的情形即为a被b整

4、除。例1设b=15,则当 a=255 时，a=17b+0,故 q=17, r=0；当 a=417 时，a=27b+12,故 q=27, r=12;当 a=-81 时，a=-6 b+9,故 q=-6, r=9。例2整数被2除的余数有两种可能：0和1 , 一个整数被2整除称为偶数，否则称为奇数，分别记作2k和2k+1, kCZ。类似地，任一整数可表示为3k, 3k+1, 3k+2三种形式之一。例 3 设 a=2t -1 ,若 a|2 n,贝U a| n。例 4 设 a, b C Z, aw0, bw0,有 x, y C Z,使 ax+by=1,证明：若 a|n , b|n , 则 ab|n。精选资

5、料，欢迎下载§ 2最大公因数与最小公倍数定义1设ai, a2,，an是n (n>2)个整数，若整数d满足d|ai ,i =1,2,，n, 则称d为ai, a2,，an的一个公因数；整数ai, a2,，an的公因数中最大的一个称为最大公因数，记作：(ai, a2,，an)；若(ai, a2,，an)=l ,则称ai, a2,，an互质(互素)；若ai, a2,，an中每两个整数互质，则称ai, a2,，an两两互质。注i任意整数ai, a2,，an必有公因数(如土 i)。注2若ai,a2,，an不全为0,则它们的公因数只有有限多个，从而它们的最大公因数必然存在而且唯一。(

6、7; i定理i之(4)注3最大公因数一定是正整数。注4 ( ai, a2,，an)=i相当于ai, a2,，a的公因数只有土 i。注5两两互质必互质，反之未然。定理i若ai,a,，an是任意n个不全为零的整数，则(1) ai,a2,，an与| ai|,| &|,| an|的公因数相同；(2) ( ai, a2,，an)=( | a|,| a2|, ,| an|)。定理2若b是任一正整数，则(1) 0 与b的公因数就是b的因数，反之亦然；(2) (0,b)=bo推论若b是任一非零整数，则(0, b)=| b|。定理3设a, b,c是任意三个不全为零的整数，且a=bq+c,其中qCZ,则a

7、, b与(b, c)有相同的公因数，从而(a, b)= ( b, c)。定理4设ai, a2,，an是不全为零的整数，则ai, a2,，an的整线性组合的精选资料，欢迎下载集合 S=aixi+a2X2+ - +anxn| Xi Z , i =1,2,，n恰由(ai, a2,，an)的所有倍数 组成。证明 因为S中有正整数，所以 S中有最小正整数，设为 D=aiXi'+a2X2'+- +anxn',则对于任意的 aixi+a2X2+anxnC S,有 aixi+a2X2+- - +anxn =( aixi'+a2X2'+ +anXn')q+r,其中

8、 0wr< aiXi'+a2X2'+anXn',于是 r=ai(xi-xi'q)+ a2(X2-X2'q)+ + an(xn-xn'q) C S,若r>0,则与D是最小正整数矛盾，故 r=0,即S中任一整 数都是D的倍数。反之，D的倍数也属于 S,故S=DZ=Da| a C Z。设 d=(ai, a2,，an),下证： D=d。由于DCS,又 d|ai, i =1,2,，n,故 d|D,即 dw D；另一方面，因为ai,a2,，anC S,所以 D|a, i =1,2,，n,从而 Dw d。因此，D=d。推论 设ai, a2,，an是

9、不全为零的整数，则存在整数xi,X2，xn,使得aiXi+a2X2+anXn=( ai, a2,，an),这一等式称为裴蜀(Bezout)等式。特别地，(ai, a2,，an)=i的充分必要条件为存在整数xi, X2，xn,使得aiXi+a2X2+ - +anXn=i 。精选资料，欢迎下载定理5 (1) a1,a2, ,an的每一个公因数都是(a1,a2, ,an)的因数； (ai,a2, ,an) (a1,a2), ,an)；(3) 设m Z ,贝U(mai,ma2, , man) m(ai,a2, ,an)； a1a2 a n(4)仅(ai,a2, , an) d,则(一,)1; d d

10、d(5)设(a, m) (b, m) 1,则(ab,m) 1;(可推广)(6) 若c|ab且(c,b) 1,则c|a。证明(1)由裴蜀等式推出；一方面由(1),另一方面由裴蜀等式；由(1)；(4)由(3)；(5)将裴蜀等式相乘；(6)由裴蜀等式或由(1), (3)可推出,c|ab, c|ac c|(ab,ac) |a|(b,c)。最大公因数的求法：1、由定理5（2）可知，求两个以上整数的最大公因数可以转化为求两个整 数的最大公因数，对此，我们有下面算法：辗转相除法（欧几里得（Euclid）算法）设a,b Z, b 0,按下述方式反复做带余除法，有限步 之后必然停止（即余数 为零）用b除a： a

11、 bq0 r0, 0 r0 |b|;用 r0除b： b r0q1 r1, 0 r1 r0;用1 除0：0 僧2 2, 0 2 1；用 rn 1 除 rn 2：n 2 n 丹n n，° n n 1 ；用n 除n 1：n 1nQn 1。则（a,b） rno事实上，由于余数满足0 1rn 10,故上述带余除法有限 步后余数必为零，另一方 面，由定理3,我们有（a,b） （b,0） （0,1）（n1，n） n。精选资料，欢迎下载2、上述算法不仅能算出(a,b),而且可以求出方程ax by (a,b)的一组 整数解，具体做法就是 将算式倒推。例 1 设 a 1859, b 1573,求(a,b

12、)及x, y。定义2设ai,a2,an是n(n 2)个非零整数，若整数 D满足ai|D, i 1,2, n,则称 D 为 a1,a2,an 的一个公倍数；a1,a2, ,an的一切公倍数中的最小正数称为a1,a2, ,an的最小公倍数，记作：a，a2, ,an。定理 6 (1) a1,a2, ,an |,|,回|;(2) a1,a2, ,an的每个公倍数都是a1,a2, ,an的倍数；(3)设 m Z ,则ma1,ma2, ,man ma1,a2,an;(4) a1,a2, ,ane？, , an ;(5) (a, b)a,b |ab|;(6)若21凡，包两两互质，则 凡，吕恒住 an |。证

13、明(1)由定义；(2)设S a1,a2,an的全体公倍数,则S恰好是S中最小正整数D的所有倍数构成的集合，故 D a1,a2, , an;(3)(4)由定义；(5)可设a,b均为正整数，当(a,b) 1时，由定义：a,b ax by,于是 b| ax (a,b) 1 b |x ab |ax a, b a,b|ab a,b ab,一般情形，设(a,b) d,则(aj) 1,于是a，鸟 怨，由(3)及定理5(3)可知d dd d d2a b a b 2 ab(a, b)a,b d( 一,一),一d d2 ab;d d d dd2(6)由(4)(5)及定理5(6)可推之。精选资料，欢迎下载补充习题：

14、1、设n Z ,则生是既约分数。 14n 32、设 n Z ,则(n! 1, (n 1)! 1) 1。3、设 m,n Z , m是奇数，证明： (2m 1, 2n 1) 1。4、设 m,n,a Z , a 1,证明：(am 1, an 1) a(m,n) 1。S设a,b是不为0< 1的整数，证明：存在x,y Z,满足ax by (a, b), 且0 |x| |b|,0 |y| |a|。6、设 a, b 乙 证明：存在 x, y,u,v Z,使得 a xu, b yv, (x, y) 1 且a,b xy°7、设 m,n Z , (m, n) 1,证明：(1) (d ,mn) (d

15、,m)(d,n);2 2) mn的任一正因数d,可唯一地表示为d d1d2,其中d1,d2分别是m,n的 正因数。8、设 n Z ,证明：(1) (an,bn) (a,b)n;(2)设(a,b) 1, a,b Z , ab cn,则a,b都是正整数的n次方哥，事实上， a (a,c)n, b (b,c)n。一般地，若若干个两 两互质的正整数之积是 整数的n次 哥，则这些整数都是正整数的n次方哥。3 设n Z , 劭正奇数，证明： (1 2n)|(1k 2knk)。精选资料，欢迎下载§ 3算术基本定理定义 一个大于1的整数，如果它的正因数只有 1及它本身，那么称之为质 数；否则称为合数

16、。注正整数分为三类：1,质数类，合数类。定理1设a Z, a 1,则a的除1外最小正因数q是一质数，并且当a是合 数时，qa。证明 假设q不是质数，则q除1及本身外还有一正因数 q1，因而1 q1 q, 但q|a,故41|2,这与q是a的除1外的最小正因数矛盾，从而q是质数。当a是合数时，a aq,其中a1 1,否则a是质数，由于q是a的除1外的最 小正因数，所以q a1，于是q2 qa a,也即q , a °定理2若p是一质数，a是任一整数，则p|a或（a,p） 1。证明 因为（p,a）|p, （p,a） 0,由质数白定义， （p,a） 1或（p,a） p, 即 p | a或（a,

17、 p） 1°推论 设a1,a2, ,an是n个整数，p是质数，若p|a1a2 an,则a1,a2, , an 中至少有一个被p整除。证明 假设a1,a2, ,an都不能被p整除，则 （p,a。 1, i 1,2, ,n, 从而 （p,a1a2 an） 1,这与 p | a1a2 an矛盾，故结论成立。定理3质数有无穷多个。（公 元前3世纪，Euclid）证明（反证法）假设质数只 有有限多个，设p1,p2, ,pr是全部质数， 考虑N p1P2 pr 1,由于N 1,故由定理1, N必有质因数p,由假设p必然 等于某个pi（1 i r）,因而p整除N p1P2pr 1,矛盾，故质数有无

18、穷 多个。定理4（算术基本定理）任一大于1的整数能表示成质数的乘积，即任一大 于1的整数a p1P2 pn, p1 p2pn,其中p1,p2, ,pn是质数，并且若a qq2 qm，qq2qm，其中 q1，q2,qm是质数，则 mn,piqi，i 1,2, ,n。证明存在性（用数学归纳法）当a 2寸，因为 端质数，所以结论成立 。精选资料，欢迎下载假设结论对小于a的正整数都成立，下面 考虑a,如果a是质数，则结论成 立；若a是合数，则有b,c Z满足a bc, 1 b a, 1 c a,由归纳假设， b,c都可以写成若干个质数 的乘积，于是a也能写成有限个质数的 乘积，适当调 动次序后便得结论

19、。唯一性 因为 a P1P2Pnqiq2 qm, PiPn, qi q2qm,所以Pi |qiq2qm，qiIP1P2Pn，于是有Pk,qj，使得 Pi|qj，qi iPk，又Pk,qj均为质数，故 Pi qj, qi Pk，又 PkPi，qj qi，故 qj Pi Pk q1，从而Pi q1,于是有p2Pn q2qm,同法可得p2 q2,依此类推，最后可得n m, Piq i 1,2, ,n。推论1任一大于1的整数a能够唯一地写成aPi1 P22Pkk， i 0, i 1,2, ,k, Pi Pj (i j)。注1上式叫做a的标准分解式；注2为了讨论的方便，我们可以插进若干质数的零次哥而写成

20、下面形式 aPi1 P22Pkk， i 0, i 1,2, ,k, PiPj (i j)。推论2设a p11P22pkk是a的标准分解式，则正整 数d是a的约数的充分必要条件是其标准分解 式为d p11P22 pkk, 0 ii，i 1,2, ,k。证明 充分性是显然的。必要性 若d 1,则结论已成立；若d 1,则由d|a可知，d的质因数必在 Pi,P2, , Pk中，于是可设d的标准分解式为d Pi1 P22Pkk,i 0, i 1,2,k。下证：i i, i 1,2, k。(反证)假设有一个 j j,则由 Pjj |d及d |a可知 Pjj j | p11 PjTPj； Pkk, 即Pj必

21、与Pi, , Pj 1, Pj 1, , Pk之一相同，矛盾，因此，i i，i 1,2, , k, 结论成立。推论3设a,b Z ,且它们的标准分解式 为 a Pi1 P22Pkk，b Pi1 P22 Pkk, i, i 0, i 1,2, , k,则(a,b)Pi1P22Pkk，其中 imin( i,)a,bPi1P22Pkk,其中 imax( i,)证明 令m p11P22pkk,则m|a, m | b,又任一公因数必整除 m,精选资料，欢迎下载 故 m (a, b)。同样可证另一结论。幼拉脱斯展纳 (Eratosthenes)筛法 任给一个正整数N,把不超过N的一 切正整数按大小关系排

22、成一串1,2,3, ,N,首先划去1,第一个留下来的是2,然 后从2起划去2的一切倍数，第一个留 下来的是3,然后从3起划去3的一切倍数，,一直到划去不超过 JN"的质数的一切倍数，最 后留下来的就是不超过 N的 一切质数。例造不超过30的质数表。补充习题1、设n 2,证明：n和n!之间必有质数，由此说 明质数有无穷多个。2、设n 2,证明：存在连续n正整数，其中每一个 都不是质数。这表明， 在正整数序列中，可以 有任意长的一段区间中 不包含质数。3、证明： 形如4m 3的质数有无穷多个；(2)形如6m 5的质数有无穷多个；4、如果p, p 2, p 褚B是质数，那么p 3。S设整数

23、10n 1 10n 21(n 1)是质数，则n必为质数，反之不成立。6、 设m Z ,证明：若2m 1为质数，则m为2的方哥；(2) 记Fn 22n 1, n 0(费马数)，证明：若 m n,则 Fn|(Fm 2);(3)证明：(Fm,Fn) 1 m n。由此说明，质数有无 穷多个。(费马数中的质数称为费 马质数，如，F0 3, F1 5, F2 17, F3 257, F4 65537都是质数，费马猜测：Fn都是质数。但F5 641 6700417不是质数 (欧拉，1732),未知：费马质数还 有吗？费马质数是否有 无穷多个？)7、(1) 设m,n Z, m,n 1,证明：若 mn 1是质数

24、，则 m 2并且n是质数；(2)设p是质数，记Mp 2p 1(梅森数)，证明：若 p q,则(Mp,Mq) 1。(梅森数中的质数称为梅 森质数(1644,法)，它与偶完全数 紧密相关，到1996年底，找到34个梅森质数，未知：是 否有无穷多个梅森质数 ?)8、设a,b,c,d Z ,满足ab cd,证明：a4 b4 c4 d4不是质数。精选资料，欢迎下载3 证明：(1) (a,b,c) (a,b),(a,c);a,(b, c)(a,b,a,c)o1 110、证明：(1) 1Z, (n 1);2 n11(2) 1 Z, (n 1)。3 2n 1精选资料，欢迎下载o§ 4函数x , x及其在数论中的一个应用定义 函数x与x是定义在