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

2020 2 2321 23 5算术基本定理 整数分解唯一性定理也称算术基本定理 在给出并证明该定理前 先介绍预备定理 定理若p为素数 则a不能被p整除当且仅当 p a 1 2020 2 2321 23 定理1 设a1 a2 an都是正整数 且p是素数 若p a1a2 an 则至少有一个ar 使得p ar 其中1 r n 证明假设ai不能被p整除 1 i n 从p是一素数和定理得到 p a1 p a2 p an 1 所以由定理5推论得到 p a1a2 an 1 这与题设p a1a2 an矛盾 故必有一ar 使得p ar 其中1 r n 2020 2 2321 23 推论 设p1 p2 pn和p都是素数 n 2 若p p1p2 pn 则至少有一个pr 使得p pr 证明由p p1p2 pn和定理1知 至少存在一个pr 使得p pr 由于pr是素数 故它只有二个正因数1和pr 由p 1和p pr 所以 p pr 2020 2 2321 23 定理2 整数分解唯一性定理 每个大于1的正整数a均可分解成有限个素数之积 并且若不计素因数的次序 其分解是唯一的 证明先证分解式的存在性 唯一性 当a 2时 分解式显然是唯一的 现设比a小的正整数其分解式均是唯一的 考虑正整数a 假设a有两个分解式a plp2 pk和a q1q2 ql 其中pl p2 pk和q1 q2 ql都是素数 2020 2 2321 23 于是p1 q1q2 ql 根据定理1知必有一qi 使得p1 qi 不妨令i 1 即p1 q1 显然p1 q1 令a a p1 则a p2p3 pk a q2q2 ql 若a 1 则a p1 q1 即a 的分解式唯一 若a 1 注意到a a 从而由归纳假设知 a 的分解式是唯一的 因此k l 并且p1 q1 pk qk 再由p1 ql 知a分解式也是唯一的 2020 2 2321 23 若将a的分解式中相同素因数合并为它的幂数 则任意大于1的整数a只能分解成一种形式 2 p1 p2 psn 1 其中p1 p2 ps是互不相同的素数 是正整数 并称其是a的标准分解式 2020 2 2321 23 推论3 使用式 2 中的记号 有 d是a的正因数的充要条件是d 3 ei Z 0 ei i 1 i s n的正倍数m必有形式m M M N i N i i 1 i s 2020 2 2321 23 推论设正整数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 min i i 1 i k a b i max i i 1 i k 2020 2 2321 23 推论4 设正整数a与b的分解式是其中p1 p2 ps是互不相同的素数 i i 1 i k 都是非负整数 则 2020 2 2321 23 推论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 都是非负整数 显然min i i 0 i i k i 1 i s 因此 对于每个i 1 i s 等式 i k i i 0与 i 0 i k i有且只有一个成立 这就证明了推论 证毕 2020 2 2321 23 推论6 设a是正整数 表示a的所有正因数的个数 若a有标准素因数分解式 2 则推论7设a是正整数 表示a的所有正因数的之和 若a有标准素因数分解式 2 则 2020 2 2321 23 例1证明 a b c a b a c 例2求 例3求 2020 2 2321 23 7函数 x 与 x n 的分解式 2020 2 2321 23 定义1 设x是实数 以 x 表示不超过x的最大整数 称它为x的整数部分 即 x 是一个整数且满足 x x x 1 又称 x x x 为x的小数部分 2020 2 2321 23 定理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 2020 2 2321 23 x 对正整数m有 设a和N是正整数 那么 正整数中被a整除的正整数的个数是 2020 2 2321 23 证明 能被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中有 2020 2 2321 23 定理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 1 n1 2 n2 3 n3 2 显然 nj就是在1 2 n中满足pj a并且pj 1a的整数a的个数 所以 由定理有 2020 2 2321 23 nj 将上式代入式 2 得到即式 1 成立 2020 2 2321 23 推论 设n是正整数 则n 其中表示对不超过n的所有素数p求积 2020 2 2321 23 例2 求20 的标准素因数分解式例320 的十进位表示中有多少个零 例4设整数aj 0 1 j s 并且n a1 a2 as 证明 n a1 a2 as 是整数 2020 2 2321 23 例5 设n是正整数 1 k n 1 则 N 3 若n是素数 则n 1 k n 1 证明由定理2 对于任意的素数