初等数论1 - 整除理论.ppt

整 除 理 论 浊伍驯英根英荚乙假班腺振褪遭派詹光愿斌瑶敬裁褂锑儿扼曲四敏鼻翰麻初等数论1 - 整除理论初等数论1 - 整除理论 1、素数 (1)、素因子 (2)、素数分布 (3)、素数搜寻 (4)、素性判定 2、GCD和LCM 走污哨萌微甲抛瘸头刨骇羌耙萎咽筒图驹唯闭羚粗瑟氧伙剩鼠镍赐全崖凭初等数论1 - 整除理论初等数论1 - 整除理论 定义 若整数a ? 0，?1，并且只有约数 ?1和 ?a，则称a是素数（或质数）； 否则称a为合数。 定理 任何大于1的整数a都至少有一个素约数。 推论 任何大于1的合数a必有一个不超过a1/2的素约数。 定理 (算术基本定理) 任何大于1的整数n可以唯一地表示成(标准分解式) 其中p1 , p2, ? , pk 是素数，p1 p2 ? pk，?1, ?2, ?, ?k是正整数。 哥德巴赫猜想：“每个大于2的偶数均可表成为两个素数之和” 陈景润： “每一个充分大的偶数都可表为一个素数及一个不超过两个素数乘积之和” 素因子 滑逊甫赁伏缎眨述蓑尧毋篷仙良瞒泰讽灰嘿说竣燕獭拽砚例谜抛屈玛犬泛初等数论1 - 整除理论初等数论1 - 整除理论 素数分布 1)、任意两个相邻的正整数n和n＋l (n＞3)中必有一个不是素数。 相邻两整数均为素数只有 2和 3。 2)、n和n＋2均为素数的有很多, 这样一对素数称为孪生素数。 在100以内有七对孪生素数: (3,5),(5,7),(11,13),(29,31),(41,43),(59,61)和(71,73)。 《自然》(2013.5.14)：新罕布什尔大学（Lecturer）（University of New Hampshire，UNH）张益唐（《数学年刊》（Annals of Mathematics））——存在无穷多对素数，其差小于7000万。 害江同嫂遁如玉甸聊麻逆芹恒栈钓雀颜擂笋姐崩叙贞体砚椒饲我裸谣访止初等数论1 - 整除理论初等数论1 - 整除理论 素数分布 1)、任意两个相邻的正整数n和n＋l (n＞3)中必有一个不是素数。 相邻两整数均为素数只有 2和 3。 2)、n和n＋2均为素数的有很多, 这样一对素数称为孪生素数。 在100以内有七对孪生素数: (3,5),(5,7),(11,13),(29,31),(41,43),(59,61)和(71,73)。 3)、 p为素数，2p-1称为Mersenne数；素数2p-1称为Mersenne素数。 p=2,3,5,7时，2p-1都是素数；p=11时， 2p-1 =2047=23×89不是素数 。 已发现最大梅森素数是p＝43,112,609的情形，一个12,978,189位数。 若an-1(a1)是素数，则a = 2，并且n是素数。(3+k)ab-1 必非素数。 4)、形如2^(2n)+1 (n = 0, 1, 2, ?)的数称为Fermat数。 Fermat曾猜测是素数：F0,F1,F2,F3,F4是素数，F5=641*6700417是合数。 5)、形如4n ? 3的素数有无限多个。 6)、越往后越稀疏：在正整数序列中, 有任意长的区间中不含有素数。 对于大于等于2的整数n，连续n-1个整数n!＋2, n!＋3, …, n!＋n都不是素数。 泵钥廖池辫瘫甄宋按潦锹粕象俘缀尼吭姓夷宦孺拂速卿芭饼孕肃形胖华乳初等数论1 - 整除理论初等数论1 - 整除理论 素数分布 7)、素数大小粗糙的估计 pn ? p1p2?pn-1 ? 1，n ? 1。 pn ? 22n。 ?(n) ? (log2n)/2。 8)、素数定理： 工吓宅溶冤扬遁筒煌仲褂悟椰闻唁残等溯系萧吻差署寞吐豁叠你壶彭径铣初等数论1 - 整除理论初等数论1 - 整除理论 素数搜寻 寻找素数的方法：Eratosthenes筛法。 袄绥知咖台扬鸣贰荣晌凉井狱掘他脑锐欣惰份值处垛估脱疯蔷舞终瑶脱挎初等数论1 - 整除理论初等数论1 - 整除理论 素性判定 确定型算法 　　试除法 尝试从2到√N