138012160904679346759444501

yangchuanju

138012160904679346759444501=701001321203*196878603121367

yangchuanju

2^67-1=147573952589676412927
147573952589676412927 = 193707721 * 761838257287

yangchuanju

M 67 的分解历史
M67=2^67-1=147 573 952 589 676 412 927
长期以来，人们不知道这个数是否为素数。
1903年，美国数学家科尔在一次著名的演讲中展示了该数的因数分解。他没有说话，只是在黑板上计算了：
147 573 952 589 676 412 927=193707721 ×761838257287
这一结果震惊了数学界，因为这表明 M67不是素数，因此不是梅森素数。
科尔通过多年的手工计算完成了这项工作，被誉为数学史上最动人的“无声演讲”。

yangchuanju

科尔是如何分解m67的？

AI智能回答
科尔分解M67的方法
1903年，数学家弗兰克·纳尔逊·科尔（Frank Nelson Cole）在一次美国数学协会的年会上，通过一次著名的无声演讲，展示了他如何分解梅森数M67（即2^67 - 1）。科尔证明了M67是一个合数，从而否定了梅森素数的猜想。他的方法主要包括以下步骤：

利用二次剩余筛选：科尔利用二次剩余的性质对可能的因子进行筛选，从而减小试除的工作量。他计算出了2^67 - 1的大量二次剩余，如2, -3, -7, 13, 37, 41, 61等。每个二次剩余的条件都可以将“试除的工作量”减少一半。

试除法：在二次剩余的帮助下，科尔试除到了大约16000000，但没有发现素因子。

Fermat方法：科尔改用Fermat方法，将数表示为两个平方数之差的形式，即n = p*q = ((p+q)/2)^2 - ((p-q)/2)^2。他使用二次剩余的条件来限制(p+q)/2所属的剩余类，并在每个剩余类里用更多的二次剩余条件做筛选，最终总的尝试次数可能只有数百次。

科尔的这一成就被认为是数学史上的佳话，他花费了三年的星期天来完成这项工作。后来，美国数学协会专门设立了科尔奖，以表彰在数论领域作出杰出贡献的数学家。

yangchuanju

分解大整数138012160904679346759444501
138012160904679346759444501=701001321203*196878603121367
要分解的大整数没有任何特征，可用吴代业法试除之，大数27位模30余1；
可能的因子是(30m+1)*(30n+1),(30m+11)*(30n+11),(30m+19)*(30n+19),(30m+29)*(30n+29),(30m+7)*(30n+13),(30m+17)*(30n+23),
若事先不知道它的素因子的任何情况，只能挨个试除（或试乘）。

现已用分解软件将其分解成两个素数积，一个模30余23，另一个模30余17；
分别令n=0,1,2,3……，以大数为被除数，30n+23为除数试除之，除至n=23366710706，方可整除，试除23366710707次；
试除过程应老老实实地逐个试除。

或令n=0,1,2,3……，m=0,1,2,3……，试乘之，乘到n=23366710706，m=6562620104045，试乘153346845451185122220522次；
实际以乘带除的操作时，在远离正确值时可免去一些试乘计算，如令n=1,2,3……亿，m=1,2,3……亿试乘看一看哪些n和m接近于待分解的整数；
然后再缩小m和n的取值间距到万、百、个，直至试乘完成。

yangchuanju

分解M67=147573952589676412927
147573952589676412927 = 193707721 * 761838257287
已经通过其它途径知道这个梅森数不是素数，
又知这个梅森数的素因子只能是2*67+1=134k+1形式的素数；
完全试除法，以M67为被除数，134k+1为除数，试除至k=144558方可除尽，试除14万4558次。
3年150个星期天，每个星期天要试除1000次，工作10小时，每小时100次左右。

如果你知道对于所有梅森数都是模8余1或7的（3除外），它们的因子也都是模8余1或7的，你可以省去一半的试除次数和时间；
2*67=134模8余6，当k=0时134k+1模8余1，当k=1,2,3,4,5,6,7,8……时134k+1模8余7,5,3,1,7,5,3,1……，余数循环出现；
不考虑模8余3和5的k值，可只取k=0,1,4,5,8,9,12,13……之值进行试除；
类似的，对于M73，2*73=146模8余2；当k=0时146k+1模8余3，当k=1,2,3,4,5,6,7,8……时146k+1模8余3,5,7,1,3,5,7,1……，余数也循环出现；
不考虑模8余3和5的k值，可只取k=0,3,4,7,8,11,12……之值进行试除；
附注：对于指数是模4余3型梅森数，它们的素因子模8余数与M67相同；对于指数是模4余1型梅森数，它们的素因子模8余数与M73相同.

Fermat方法，将数表示为两个平方数之差的形式，即n=p*q=((p+q)/2)^2-((p-q)/2)^2= ((p+q)/2)+(p-q)/2))*((p+q)/2)-(p-q)/2))=p*q
反算之，知
p        761838257287
q        193707721
(p+q)/2        381015982504
(p-q)/2        380822274783
((p+q)/2)^2        145173178923488434110016
((p-q)/2)^2        145025604970898757697089
相减        147573952589676412927
然而当时科尔要找到M67=381015982504^2-380822274783^2，容易吗？