初等数论第一章整除5-7.ppt

2019/8/5 09:10,5 算术基本定理,整数分解唯一性定理也称算术基本定理, 在给 出并证明该定理前, 先介绍预备定理. 定理 若p为素数, 则a不能被p整除当且仅当: (p,a)=1,2019/8/5 09:10,定理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.,2019/8/5 09:10,推论,设p1,p2,pn和p都是素数, n2. 若p|p1p2pn, 则至少有一个pr, 使得p=pr. 证明 由p| p1p2pn和定理1知, 至少存在一个pr, 使得p|pr. 由于pr是素数, 故它只有二个正因数1 和pr. 由p1和p| pr, 所以: p= pr.,2019/8/5 09:10,定理2 (整数分解唯一性定理),每个大于1的正整数a均可分解成有限个素数 之积, 并且若不计素因数的次序, 其分解是唯 一的. 证明 先证分解式的存在性. 唯一性. 当a=2时, 分解式显然是唯一的. 现设 比a小的正整数其分解式均是唯一的. 考虑正 整数 a, 假设 a有两个分解式 a=plp2pk和 a=q1q2ql, 其中pl,p2,pk和q1,q2,ql都是素 数.,2019/8/5 09:10,于是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分解式也是 唯一的.,2019/8/5 09:10,若将a的分解式中相同素因数合并为它的幂 数, 则任意大于1的整数a只能分解成一种形 式: (2) p1 p2 ps n1, 其中p1,p2,ps是互不相同的素数, , , 是正整数. 并称其是 a的标准分解式.,2019/8/5 09:10,推论3,使用式(2)中的记号，有 () d 是a的正因数的充要条件是 d = (3) eiZ，0 ei i，1 i s； () n的正倍数m必有形式 m = M，MN，iN， i i，1 i s。,2019/8/5 09:10,推论 设正整数a与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。,2019/8/5 09:10,推论4,设正整数a与b的分解式是 其中p1, p2, , ps 是互不相同的素数，i，i （1 i k）都是非负整数，则,2019/8/5 09:10,推论5,设a，b，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有且只有一个成立。 这就证明了推论。证毕。,2019/8/5 09:10,推论6,设a是正整数， 表示a的所有正因数的个数.若a有 标准素因数分解式(2)，则 推论7 设a是正整数， 表示a的所有正因数的之和. 若a有标准素因数分解式(2)，则,2019/8/5 09:10,例1 证明：（a,b,c)=(a,b),(a,c),例2 求 ， 例3 求,2019/8/5 09:10,7 函数x与x , n!的分解式,2019/8/5 09:10,定义1,设x是实数，以x表示不超过x的最大整数， 称它为x的整数部分，即x是一个整数且满足 x x x+1. 又称x = x x为x的小数部分。,2019/8/5 09:10,定理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 = ；,2019/8/5 09:10,x = . ()对正整数m有 ()设a和N是正整数.那么，正整数 中被a整除的正整数的个数是,2019/8/5 09:10,证明,能被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 b 中有,2019/8/5 09:10,定理2,设n是正整数，n! = 是n!的标准分解 式，则 i = (1) 证明 对于任意固定的素数p，以p(k)表示在k的标准分 解式中的p的指数，则 p(n!) = p(1) p(2) p(n). 以nj表示p(1), p(2), , p(n)中指数等于j的个数，那么 p(n!) = 1n1 2n2 3n3 ， (2) 显然，nj就是在1, 2, , n中满足pja并且pj + 1 a的整 数a的个数，所以，由定理有,2019/8/5 09:10,nj = 将上式代入式(2)，得到即式(1)成立。,2019/8/5 09:10,推论,设n是正整数，则 n! = ， 其中 表示对不超过n的所有素数p求积。,2019/8/5 09:10,例2,求20！的标准素因数分解式 例3 20！的十进位表示中有多少个零？ 例4 设整数aj0(1 j s),并且 n=a1+a2+as.证明：n!/a1!a2! as!是整数.,2019/8/5 09:10,例5,设n是正整数，1 k n 1，则 N (3) 若n是素数，则n ，1 k n 1. 证明 由定理2，对于任意的素数p，整数n!，k!与 (n k)!的