Wednesday, December 9, 2009

欧拉是如何做到的?(二)--F5的因式分解

原文http://www.maa.org/editorial/euler/How%20Euler%20Did%20It%2041%20factoring%20F5.pdf



在数论的历史长河中,有两个人的名字永远也不会被人给忘记。Pierre de Fermat(1601-1665)[费尔马]和Leonhard Euler(1703-1783)[欧拉]。费尔马是一个伟大的“山寨”数学家,他与笛卡尔是同一个时代的人物,但他们两位老兄可是一对冤家。费尔马的正当职业是一名法官(法国)。在那个年代,法官是不被提倡参与太多的社交活动的,因为相交往的亲朋好友有一天可能对簿公堂,这样会影响法律的公正性。所以费尔马住在一个远离喧嚣的地方,过着离群索居的日子,因此他也就有了充裕的时间来进行他感兴趣的数学研究。他主要是通过与另外一名数学家Marin Mersenne[梅森]的通信来了解数学界的最新动态。






费尔马与笛卡尔[1596-1650]在许多领域都有着一样的兴趣。他们都各自独立创立了解析几何学,但是费尔马很少发表自己的发现,因此解析几何的坐标系用了笛卡尔的名字,而不是费尔马的。他们俩都试图复原阿波罗尼斯失传的书籍。当费尔马找到一对亲和数的时候,笛卡尔则以另外一对亲和数做为反击。他们俩都找到了过给定曲线上的一点的切线的方法,并且费尔马展示了如何求取形如y=x^{n} (n不等于-1)的曲线下与坐标轴所围的面积。所有的这些都为十七世纪后期的微积分的发现打下了重要的基础。但是这两位老兄互相都看不顺眼,而且似乎笛卡尔讨厌费尔马的程度比费尔马讨厌笛卡尔的程度更甚(这个八卦我喜欢)。他们两人好像一生都未见过面。






费尔马沿袭着许多十七世纪的数学传统。相对于给出一个证明,费尔马更喜欢只是简单的给出一个结果,而把证明留给他的读者,好像是对读者的一个挑战。有的时候,他会在书的页边空白处写下他的一些笔记。1666年,费尔马去世以后,这些笔记随着他的儿子将其公开出版,而在数学界变的闻名于世。这就是那个著名的猜想-费尔马大定理--为什么被世人所知的原因。(原文是Fermat Last Theorem,但翻译的就是费尔马大定理)。费尔马有很多的猜想,但没有一个猜想在重要性和影响力上能与之匹敌。例如在他的另外的一个笔记中,他写到:


除了1以外的三角形数,都不能被写成四次幂的形式。(三角形数就是\sum_{1}^{n}{n}


这个结论看起来十分的有趣,但是重要性是无法与费尔马大定理相提并论的。


费尔马大定理:任何一个数的立方,不能分成两个数的立方之和;任何一个数的四次方,不能分成两个数的四次方之和,一般来说,不可能将一个高于二次的幂分成两个同次的幂之和






在1738年,Euler证明了费尔马大定理的特殊情况。他在他的职业生涯中,证明了费尔马几乎所有的猜想,包括了费尔马小定理,以及费尔马大定理在n=3,4的特殊情况。费尔马最后定理(原文是Fermat Last Theorem,这里又改称最后定理,与下一句话有关)之所以被成为“最后定理”,并不是因为它是费尔马最后提出的猜想,而是因为在Euler之后,这是最后一个未被证明正确或是错误的重要定理。(该定理在九十年代已经被证明。)




Euler对于数论的兴趣最早是被费尔马的另外一个猜想所激发的:对于所有的正整数n,F_{n}=2^{2^{n}}+1  为质数。费尔马在1630到1640年的多份信件中提到这个猜想。如今这些数被称为费尔马数。当n比较小的时候,F_{n} 确实是质数,例如3,5,17,257,65537,都是质数。但当n=5的时候,F_{n} 为4294967297.






Euler在圣彼得堡的导师歌德巴赫(这个名字是不是有点如雷贯耳,没错,他就是Euler的导师),曾经在1729年的时候让Euler注意这个猜想。Euler但是的第一反应就是他不可能在这个问题上能有什么大的进展。但是仅仅过了三年,1732年的时候,就在费尔马提出这个猜想快一百年的时候,Euler给出了他的答案,费尔马是错的。每当看到Euler犹如割菜一般的给出各个成就是,我的眼前就涌现出一条谚语“彪悍的人生是不需要解释的”。在Euler的第一篇数论论文中,Euler指出,4294967297能够被641整除。在这篇文章的后半部分,Euler又提出了自己的六个猜想,其中的一些与费尔马小定理是等价的。


例如:如果p为质数,并且p不能整除a,那么p能够整除a^{p-1}-1 .






但是Euler在论文中并没有告诉我们如何想到用641去除4294967297.他一定不是一个个用质数依次去试直到641.他一定有着更好的方法,而他直到15年之后才揭晓这个秘密。






在他这个十五年之后的论文中,Euler给出了他对费尔马小定理的第一个证明,但是我们会关注这篇论文的其它部分。他证明的费尔马小定理更为一般的形式:


命题四:如果a和b都不能被质数p整除,那么a^{p-1} -b^{p-1将会被p整除。

他利用这个定理去证明另外的一个定理:


命题五:两个平方数之和aa+bb,不能被形如4n-1的质数整除,除非a和b都能被4n-1整除。

Euler对这个定理的逆命题十分的感兴趣:如果a和b都没有一个相同的形如4n-1的质因数,那么aa+bb的所有的奇质因数都将数4n+1的形式。






Euler在命题6 7对命题5 的逆命题做了拓展成为四次幂(只能被形如8n+1的奇质因数整除)和八次幂(只能被形如16n+1的奇质因数整除),随后他给出了更为一般的形式:


命题八:a^{2^{m} } +b^{2^{m} } 之和,只能被形如2^{m+1}n+1 的因子整除。






Euler在这里叙述两个数之和的时候有些不够严谨,或者说他漏掉了一些的先决条件。他的本意应该是a和b是互质的。






正如Euler所说的,这些命题给我们提供了一个分解2^{2^{5} } +1(4294967297)的方法。例如,4294967296和1都是2的三十二次幂,并且它们互质,而且2^{5} =32,通过Euler的命题八,我们能够知道4294967297的素因子必然为64n+1形式。我们可以简单的依次增加n的值,并验证64n+1是否为4294967297的因子,直到64n+1超过4294967297的平方根。下面我们可以来试试:


n=1 64n+1=65 65不是素数


n=2 64n+1=129 129不是素数


n=3 64n+1=193 193为素数,但不能整除4294967297


n=4 64n+1=257 257为素数,但不能整除4294967297


n=5 64n+1=321 321不是素数


n=6 64n+1=385 385不是素数


n=7 64n+1=449 449为素数,但不能整除4294967297


n=8 64n+1=513 513不是素数


n=9 64n+1=577 577为素数,但不能整除4294967297


n=10 64n+1=641 641能整除4294967297且是素数




Euler没有提到另外的一个素因子6700417是否为素数.这个数为素数,当属没有证据显示Euler曾经尝试寻找这个素因子。






证明6700417是素数需要做多少工作?实际上并不太多。如果6700417有素因子的话,那么它一定比6700417的平方根小,也就是大概为2588,并且根据命题八,任意的形式的因子都为64n+1。形如64n+1小于2588的整数有40个,我们已经检验过其中的10个了,还有30,并且其中的769,1153,1217,1409,1601,2113为素数,没有一个能整除6700417.Euler已经提我们完成了大半部分的工作了,我们只需要用纸和笔,花上几分钟证明6700417数素数就能完成这个证明了。






6700417是Euler那个时代所知的最大质数。1762年的时候,Euler制作了一张大素数表,其中他提到的最大素数为232037.有一些学者认为Euler知道6700417是素数,因为证明这个数为素数,对于他来讲实在是小菜一碟。另外的一些学者认为Euler从来就没有想过要在这个特殊的数字上使用这些命题,如果他做过,他一定会告诉他人或是在文章中有所记录。对于这一看法,众学者纷纷表示反对。

No comments:

Post a Comment