一些关于素数和因数分解的文章。

【因数的分解】

    在于1903年10月美国数学会举行的一次会议日程上,安排了数学家F.N.科尔提交的一篇论文,题目叫做"关于大数的因子分解".当轮到他演说时,科尔来到黑板前面,一言不发地做起了2的乘幂演算,直至2的67次幂,然后减去1;他又将如下2个数的乘积演算出来:
                193707721和761838257287
    两次演算结果完全相同.然后他又默默地回到了自己的座位上,全体听众顿时爆发出热烈的掌声,这是数学史绝无仅有的一次无声的报告.
       那么,如何去找合数的因子呢?试除法显然不适用于大数的因数分解,但实际上,目前所有用于素性检验和因数分解的方法中又都少不了试除法.一般在开始时它的运算并不慢,比如先用前一百万个素数去试除,如果找到一个因数,那么素性和因数分解问题就都解决了.若未找到,这时他如果是合数,就只有极大的因数,费马曾经找到了一种极其简单的对付这种情况的方法,以下就是这种方法的简单说明:
    设n=uv,u和v都是大的奇数,不妨设u<=v令x=(u+v)/2,y=(v-u)/2.于是,0<=y<x<=n,且v=x+y,u=x-y故n=uv=(x+y)(x-y)=x*x-y*y或者       y*y=x*x-n,若能找到两个数x,y满足前式,则 n=(x+y)(x-y),即得出了n 的因数分解.费马本人就是用此方法找到了2027651281=44021X46061.可以这样进行,找出k>=√n 然后从x=k 开始,依次检验x=k+1,x=k+2...这些数是否能使x*x-n成为平方数,一旦找到这样的x,当然分解工作就完成了.倘若n有两个大小相近的因数,则其中之一能很快找到.你可以用此方法试着分解一下10379.另外,在判断x*x-n是否是平方数时,可以排除个位数是2,3,7,8的情况,因为没有一个平方数是以2,3,7,8结尾的.
    另一种方法是所谓"排除元"法,首先若一个数能够表示成x2+ky2时,则其因子也必有同样的形式:
      (x2+ky2)(m2+kn2)=(xm-kyn)2+k(xn+ym)2
    反之,若待分解的数 N=a2+kb2=c2+kd2 则有:
       N=k(ad+bc)(ad-bc)/(a+c)(a-c) 或者
       N=k(ad+bc)(ad-bc)/(d+b)(d-b)
    在x2+ky2中,k=4,2,-2时相应的二次形式x2+4y2,x2+2y2,x2-2y2可以表示一切奇整数.第一个可以表示8x+1或8x+5形式的整数,第二个形式表示8x+1或8x+3形式的整数;第三个形式表示8x+1或8x+7形式的整数.例如45677=5 mod 8,所以应取x2+4y2,的形式.由此y<107,为了减少探查值,将5作为第一个排除元,对5篇模:

                           45677-4y2=2-4y2=x2 mod 5

    对于y=5z,5z+1,5z+4得出5的非平方剩余,即方程无解,只有y=5z+2,5z+3才有解.继续使用排除元7.8,9,11(素数或素数的乘幂)使得y只能是7,17,23,27,53,67,77之一.最后:
                           45677=2112+4*172 
    其他的y值都不是平方数.因此45677是一个素数.
    再看36661同样是8x+1形式,找出不定方程x2+4y2=36661的解:36661=1692+4*452=1192+4*752
所以a=169,b=45,c=119,d=75.最后36661=(169*75+45*119)(169*75-45*119)/288*50=61*601.