初等数论第一章整除

1、初等数论第一章整除 2022/9/3 *第1页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *定理1设a1,a2,an都是正整数,且p是素数. 若p|a1a2an,则至少有一个ar, 使得p|ar, 其中1rn.证明 假设 ai不能被p整除, 1in. 从p是一素数和定理得到(p,a1)=(p,a2)=(p,an)=1. 所以由定理5推论得到(p,a1a2an)=1, 这与题设p|a1a2an矛盾, 故必有一ar, 使得p|ar, 其中1rn.第2页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *推论设p1,p2,pn和p都是素数,

2、n2. 若p|p1p2pn, 则至少有一个pr, 使得p=pr.证明 由p| p1p2pn和定理1知, 至少存在一个pr, 使得p|pr. 由于pr是素数, 故它只有二个正因数1和pr. 由p1和p| pr, 所以: p= pr.第3页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *定理2 (整数分解唯一性定理)每个大于1的正整数a均可分解成有限个素数之积, 并且若不计素因数的次序, 其分解是唯一的.证明 先证分解式的存在性. 唯一性. 当a=2时, 分解式显然是唯一的. 现设比a小的正整数其分解式均是唯一的. 考虑正整数 a, 假设 a有两个分解式 a=plp2

3、pk和a=q1q2ql, 其中pl,p2,pk和q1,q2,ql都是素数.第4页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *于是p1| q1q2ql , 根据定理1知必有一qi, , 使得p1|qi，不妨令i=1, 即p1|q1, 显然p1=q1. 令a=a/p1,则a=p2p3pk, aq2q2ql. 若a=1, 则a= p1=q1,即a的分解式唯一. 若a1, 注意到aa, 从而由归纳假设知, a的分解式是唯一的. 因此k=l,并且 p1=q1,pk=qk, 再由p1=ql, 知a分解式也是唯一的.第5页，共23页，2022年，5月20日，13点35分，星

4、期一 2022/9/3 *若将a的分解式中相同素因数合并为它的幂数, 则任意大于1的整数a只能分解成一种形式: (2)p1 p2 psn1, 其中p1,p2,ps是互不相同的素数, , , 是正整数. 并称其是 a的标准分解式.第6页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *推论3使用式(2)中的记号，有() d 是a的正因数的充要条件是 d = (3) eiZ，0 ei i，1 i s；() n的正倍数m必有形式m = M，MN，iN，i i，1 i s。第7页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *推论 设正整数a与

5、b的标准分解式是 其中pi (1 i k)，qi (1 i l)与ri (1 i s)是两两不相同的素数, i , i (1 i k), i(1 i l)与i（1 i s）都是非负整数，则(a, b) = ， i = mini, i, 1 i k，a, b = ， i = maxi, i，1 i k。第8页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *推论4设正整数a与b的分解式是其中p1, p2, , ps 是互不相同的素数，i，i（1 i k）都是非负整数，则第9页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *推论5设a，b，

6、c，k是正整数，ab = ck ，(a, b) = 1，则存在正整数u，v，使得a = uk，b = vk，c = uv，(u, v) = 1。证明 设 ，其中p1, p2, , ps 是互不相同的素数， i （1 i s）是正整数。又设 其中i ，i（1 i s）都是非负整数。显然mini , i = 0， i i = k i ，1 i s，因此，对于每个i（1 i s），等式i = ki ，i = 0与i = 0，i = ki有且只有一个成立。这就证明了推论。证毕。第10页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *推论6设a是正整数， 表示a的所有正因数

7、的个数.若a有标准素因数分解式(2)，则推论7 设a是正整数， 表示a的所有正因数的之和.若a有标准素因数分解式(2)，则第11页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *例1 证明：（a,b,c)=(a,b),(a,c)例2 求 ，例3 求第12页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *7 函数x与x , n!的分解式第13页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *定义1设x是实数，以x表示不超过x的最大整数，称它为x的整数部分，即x是一个整数且满足 x x x+1.又称x = x

8、 x为x的小数部分。 第14页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *定理1 设x与y是实数，则() x y x y；() 若x=m+v, m是整数， 0 v 1, 则m= x, v=x，特别地，若0 x 1，则x = 0，x =x ；() 若m是整数，则m x = m x；() x y = ；() x = ；第15页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *x = .()对正整数m有()设a和N是正整数.那么，正整数中被a整除的正整数的个数是第16页，共23页，2022年，5月20日，13点35分，星期一 2022/9

9、/3 *证明能被a整除的正整数是a, 2a, 3a, ，因此，若数1, 2, , N中能被a整除的整数有k个，则ka N (k 1)a k N/a k 1 k = 证毕。由以上结论我们看到，若b是正整数，那么对于任意的整数a，有即在带余数除法 a = bq r，0 r 0(1 j s),并且n=a1+a2+as.证明：n!/a1!a2! as!是整数.第21页，共23页，2022年，5月20日，13点35分，星期一 2022/9/3 *例5设n是正整数，1 k n 1，则 N (3)若n是素数，则n ，1 k n 1.证明 由定理2，对于任意的素数p，整数n!，k!与(n k)!的标准分解式中所含的p的指数分别是利用例4可知第22页，共23页，2022年，5月20日，13点35分，星期一