《793编号高中数学竞赛专题8-15》由会员分享，可在线阅读，更多相关《793编号高中数学竞赛专题8-15（76页珍藏版）》请在金锄头文库上搜索。
1、专题八 数学奥林匹克专题讲座数学奥林匹克专题讲座-素数素数 上海市上海中学上海市上海中学 顾滨顾滨 素数是数论中核心的问题之一， 因为素数的定义如此简单， 分布却如此不规律. 关于素数，我们知道的也很少，接下来我们将介绍有关素数的一些核心问题，并 对其中一些加以讨论. 一.关于素数无穷多. Euclid 第一个证明了：素数有无穷多个. 【定理 1（Euclid） 】：素有无穷多个. 它的证明是很经典的无穷递推法，当然目前也有其它证法，有兴趣的同学可以 参看 The proof from the book一书， 这里就略去了.下面我们来证明更强的结论 ： 【定理 2（Euler） 】 （这里表示
2、对所有的素数求和，以后类同） 1 pp p 证明 ： 首先证明 Euler 恒等式 ： 设实数， 则 （1s 2 1 111 1 sss npppn 表示对所有的素数求积，以后类同）. p 我们已经熟知当时， 上式的右边的级数是绝对收敛的， 而由于算术基本定1s 理，若将上式左边逐项展开，则对每个 n，由于 n 恰有唯一的一种方法表为 ，因此恰出现一次，即证得 Euler 恒等式. 12 12 p p 1 s n 现 将Euler 恒 等 式 化 为 ：.两 边 取 对 数 得 1 1 1 s ss np p pn .利用不等式得： 1 1 lnln() 1 s ss pn p pn ln(1
3、)xx .令即知，又 1 1 11 lnln() 1 s sss ppn p ppn 1s 1 11 ln() 1pnpn ，故成立. 111 1 1(1)ppppppp 1 pp Euler 这一证明有着很浓的解析色彩，将孤单的素数与全体正整数通过式联 系起来了，我们在后面证明 Dirichlet 定理时将用到一样的思想.另外利用式可 以证明任取两数互素的概率为，但这已经离开主题较远，暂不考虑. 2 6 为了以后的需要，我们先来定义一些函数： 若，则定义函数 12 12 (1,1,2, ) k kj np ppjk ； 12 111 ( )(1)(1)(1) n nn ppp 定义函数；以及
4、函数.以下我们一般以( )ln p x xp ln,1; ( ) 0, m pnpm n 若 其他情况 表示正整数，表示素数，表示约数.xpd 关于， 我们显然有（这里表示为对 n 的所有正约数求和） ，( )nln( )( ) d n nd 因此我们有： （交换和号值得ln( !)ln( )( )1( ) n xn x d nd xd nd x n x x xxddd d 注意） 因此结合可知：lnln( !)lnnnnnnn ( ) ( ) ( ( ) )ln( !ln( )( )( ) dddd xd xxxx dxxx xddx x xxO xd d d dddd , (这里表示至多与
5、同阶，即存在使),( )O xx 12 ,C CR 12 ln( !)lnC xxxxC x 又因为 (这一等式详见第二个问题)因此,( ) ( )( ) d xd x x ddO x d ，故知. ( ) ln( ) d x d xxxO x d ( ) ln(1) d x d xO d 更进一步，由于 2 2 2 1 ( )lnlnlnln1 (1) 1 (1)(1)! 1 d xp xp px dppppp O dpppp pp p p 故，或者我们可记 ln ln(1) p x p xO p 11 ln ln( ),( )(1) p x p xr xr xO p 式应该说是关于素数分布
6、的最基本的等式之一，由它可以导出许多有用的结果. 现在，我们就来证明定理 2 的加强形式: 【 定 理3】 ：其 中,而 2 1 lnln( ), p x xAr x p 1 2 2 ( ) 1 lnln2 ln r t Adt tt ， 2 1 ( )() ln r xO x (注:说明收敛) 1( ) (1)r tO 1 2 2 ( ) ln r t dt tt 【证明】：我们有 2 2 11ln111 ( ) 2ln2ln x p xp x p df t pppt 2 11(2)1 ( )( ) 2lnln2ln x f f xf t d xt （其中在上仅在 t 在为素数时不可微， 然
7、而当 t 为素数时可以 ln ( ) p t p f t p 2, )x 形式得认为此时；这一步运用了 Abel 求和的思想）,从而利用分部积 ln ( ) t f t t 分公式可得: 1111 22 222 ln( )( )ln( )( )( )( )111 1 2ln2lnlnlnln xxx xr xtr tr xr t dtdtdt xttxtttt 11 22 2 ( )( )1 1()lnlnlnln2 lnlnln x r tr t Oxdtdt xtttt 又因为,因此我们就得到了定理 3！ 1 22 ( )11 ()() lnlnln xx r t dtOdtO ttttx
8、 二二.关于:( )x 对大于 2 的实数 x，令为不大于 x 的素数个数,C.F.Gauss 在一百多年前( )x 提出了著名的猜想： 【素数定理】：. ( ) ( ) ()(1) ln ln lim x x x xx x x x 即 我们先来简要回顾一下素数定理的提出与解决过程： 1850 年，Chebyshev 证明：存在正常数使; 12 ,C C 12 ( ) lnln xx CxC xx 1859 年，Rieman 在其论文中提出素数定理与 Rieman 的函数的关系( ) s ，在复分析中可将解析开拓至全体复数 s） ，将数论与复变函数 1 1 ( ) s n x n ( ) s
9、联系在了一起.(Euler恒等式已初步体现了分析思想)1896年， Hadamard和Poisson 各自独立地运用复分析证明了素数定理.（其中一个关键点是的零点 s 的实( ) s 部必小于 1 而大于 0，而 Riemann 猜想是说这样的零点 s 的实部均为）; 1 2 1896 年，Selberg 和 Erdos 独立给出了素数定理的初等证明.我们将不会证明素数 定理，只因复分析直观而艰深；初等方法复杂而难以理解.在这一节中，我们将 讨论 Chebyshev 不等式，并以此引入一些基本的解析数论技巧. 【定理 4(Chebyshev)】：设，则.2x ln25 ( )ln22 3ln2
10、ln xx x xx 【证明】：以, 2 ( , )! m p nnpM m 表示 中含 的幂，考虑 则 , 2 lnln(2 )!)2ln( !)ln ( ,2 )2 ( ,)ln p mm pm Mmmppmp mp (注意 pm 时，M 中恰含一个 p) 而对, 1 2 , ( ,2 )2 ( ,)(2) jj j mm pmpmp m pp ln2 1 ln 2ln2 (2) ln jj m j p mmm ppp 代入知,也即ln( ) ln2(2 )( ) ln2Mmmmmm ,ln(2 ) ln(2 )Mmm 另一方面，, 2 2 2222 2 (2) 0122 m m mmmm
11、 M mmm 考虑 于是知 , 2ln2 (2 ) ln(2 )ln2ln2ln(2 )(2 )1 ln(2 ) m mmMmmm m 取，由并对较小的 x 作检验即可得左半边不等式;再来证右半边，同样 2 x m 由知,又,故知 2 lnln(2 )( ) ln m pm Mpmmm 2 2 2 m m M m , 2ln2 (2 )( ) ln m mm m 同理考察 , 21 2ln2 (21)(1) ln(1) m m Mmm mm 知 现在右半式对成立，而当时递增，故只须考虑,利用并3x 3x ln x x * xN 对右半式归纳知：（经检验对均成立）若，则2000 x 2xm 52
12、ln2 ( )( )(2 )( )ln22 2lnln mm xmmm mm 5210 ln22(ln2ln512) 2ln(2 )9 m mmm m 最后一式 若，类似可证！21xm 于是我们证明了 Chebyshev 不等式，也就说明了素数的上密度为 0. 顺便指出，由我们得到. 2 lnln2ln2 m pm pMm 考虑,于是结合归纳法 （具体细节略去） 121 21 ln2ln2 mpm m Mpm m 类似知 可知 ,这是一个很好的渐近公式，尽管ln2ln2( )2ln2 p x pxxx 也就是 我们将看到，应有 ( ) lim1 x x x 【定理 5】：素数定理.( ) ()
13、xx x 【证明】： ,余下只需( )lnlnln( )lnln p xp xp xp x xx xpxxx pp 估计,ln p x x p 事实上， lnln lnlnln xx p x pp x xx xxx ppp () lnlnln( )() ln x xxx x 这一步很关键 2 ln (lnlnln) ln ln() ln x x x Cxx x x x lnln () ln xx O x 结合即知定理 3.3 成立！ Erdos 和 Selberg 正是通过证明才最终得到了素数定理的初等证明. 三.关于 Dirichlet 定理代数方法证明 前面围绕 “素数有无穷多个” 这一主
14、题展开讨论， 如果考虑特殊序列中的素数， 问题就很不简单了.一个最基本的问题是等差数列中素数是否有(0,1,)knl n 无穷多个？（这和陶哲轩的定理惊人地类似，k 是“素数”和“等差数列”颠倒 了一下）,我们有： 【定理 6(Dirichlet 1837)】：设中有无穷多个素数.( , )1,(0,1,)k lknl n则数列 在这里，先来讨论 Dirichlet 定理的一些特殊情况，先从 Euclid 方法谈起： 【定理 7】：存在无穷多个模 3 余 2 的素数，也存在无穷多个模 4 余 3 的素数. 【证明】：首先这样的素数必存在，假设有 , 1212 ,2(mod3),(5) k p
15、pppp 考虑，它必含有一个模 3 余 2 的素因子，且异于，对模 4 12 32 k p pp 1k pp 余 3，同样地考虑既可！下面我们引入多项式方法： 12 43 k p pp 首先大家熟悉二次剩余的概念，我们在此引入 Legrendre 符号： 设 p 为素数，q 为正整数，令 1, 0, 1, qp q qp p qp 若 为模 的二次剩余； ，若 若 为模 的二次非剩余 不加证明地指出：, 1,1(mod4) 1 ( 1,3(mod4) p Euler pp 若 判别法） 若 , 1,17(mod8) 2 1,35(mod8) p pp 若， 若， 及关于奇素数的二次互反律（属于 Gauss）：. 11 22 ( 1) pq qp pq 【定理 8】：(i)存在无穷多个模 8 余 7 的素数; (ii)存在无穷多个模 5 余 4 的素数. 【证明】：(i)若有 2 112 7(mod8),()2 kk ppMp pp考虑数 任取素数有，因此p M 2 12 ()2 1 k p pp
