整数的因数分解zhengshu de yinshu fenjie

把一个整数分解为若干因数乘积的方法.利用整数的素因数分解式求两个或两个以上整数的最大公因数和最小公倍数，是非常方便的.用来求一个整数的因数个数和因数和也不困难.但要求出一个整数的素因数分解式，却没有简便易行的一般方法.特别是大整数的因数分解是很困难的.
由于大整数的因数分解，在理论上和实际应用上都很有价值，因此它仍然是近代数论研究的重要课题.
对于不太大的整数N进行因数分解，一般可按照素数表用2,3,5,7，…等素数去试除N，直到试验到不超过的最大素数为止，就一定能求出N的素因数分解式.对大整数N，较好的方法是查因子表.最大的一个因子表是由莱梅制成的.他给出了直到10⁷的每个整数的最小素因数，利用这个表就可以求出不超过10⁷的整数N的素因数分解式(参看D.N.Lehmer,Factor,table for the first ten millions,Carnegie Institute,Wasington,1909).
为了对较大的整数N进行因数分解，目前已有许多减少试验次数的方法，但这些方法大都需要较多的数论知识.费尔马方法比较简单，其原理也不复杂：
为了对奇的合数N进行因数分解，若能把N表成N=x²-y²(x-y>1)的形式，则可以分解为N=(x-y)(x+y).怎样把N表成两个完全平方数之差？要先求出最小的正整数m，使m2>N，然后依次造一列数：m²-N,(m+1)²-N,(m+2)²-N，…，当出现一个完全平方数(m+i)²-N时，即得，x²＝(m+i)²,y²＝(m+i)²-N.如，N=9 271，它在96²和97²之间，所以m=97. 依次计算：97²-N=138,98²-N=333,99²-N=530,100²-N=729=27²，即x²＝100²,y²＝27²，那么x-y=73,x+y=127，于是得到9 271=100²-27²＝73×127.查素数表可知，73和127都是素数.这个方法对于N有两个差不多大小的因数的情形，比较容易得出结果.