判断 (10^1146 -1) / (9×2293) 是否为素数。

天山草

有一个办法不知行不行。将原数分子中的 10 换成 x，分母先不考虑。将分子进行因式分解，结果是：

moranhuishou

下面引用由天山草在 2013/09/24 09:49am 发表的内容：
到目前为止，找出了原数的 17 个因子。原数（1142 位）除以这些因子之后，得到一个 1003 位的数，这个数仍是合数...

一般说来，一个1000位的大数是不可能“瞬间”判定素性的（道理是：如果这么大数都能“瞬间”判定，那发现大素数也就不成什么问题了）。除非这个数有小因子可以分解，我估计你的这个软件判定有如下问题：
就是凡是超出软件的判定的位数的数字，无论它是什么数一概“瞬间”判定为“合数”，这样判定“正确”的概率是很高的，因为绝大多数都是合数。
当然，这只是猜测。

天山草

[这个贴子最后由天山草在 2013/09/24 07:26pm 第 5 次编辑]


这样，令 x=10，原数的分子有以下因数（不一定是质因数，实际上只有 11 是质数，别的都是合数，需要进一步分解）构成：
（1）9；
（2）11；
（3）91；
（4）111；
（5）9090909090909090909090909090909090909090909090909090909090909090909090\
9090909090909090909090909090909090909090909090909090909090909090909090\
90909090909090909090909090909090909090909090909091；
（6）1111111111111111111111111111111111111111111111111111111111111111111111\
1111111111111111111111111111111111111111111111111111111111111111111111\
111111111111111111111111111111111111111111111111111；
（7）90090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090090990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990990991；
（8）1098901098901098901098901098901098901098901098901098901098901098901098\
9010989010989010989010989010989010989010989010989010989010989010989010\
9890109890109890109890109890109890109890109890109889010989010989010989\
0109890109890109890109890109890109890109890109890109890109890109890109\
8901098901098901098901098901098901098901098901098901098901098901098901\
0989010989010989010989010989011；
说明：
（1）是 9，正好与原数分母中的 9 相消。
原数分母中还有个 2293，这是一个素数。而（8）中可以分解出一个 2293 的因数，正好与分母中的 2293 相消。这样，（8）可以简化成（8a），它等于：47924164801617919803702620972573000484034064496340990017396471822987304888744051413043999175704365412171779376314919271744391674614090662934971700780684644618355913602315695643214177884914910166153079367209327959436986911910592678146101608814212390313567810296986049275626249023545142167034883999559097683825115137805935887052328395546886606633662891839952459228516795023554727。
   至此，只需要考虑（2），（3），（4），（5），（6），（7），（8a）的分解，其中前三个不在话下，只需要考虑后四个数的分解。
   不过可能还是有困难的。所谓困难，就是需要太多的时间，如果时间很久，比如说 2 天，就算是做不出吧。

天山草

不过，还有办法。那就是利用已知的 17 个因数。

天山草

[这个贴子最后由天山草在 2013/09/24 08:59pm 第 4 次编辑]


利用已知的因数112103021940812743353521，可找到（6）中有这个因子。消去该因子后，商为9911517922306739118369675928363553137976174417944341744617135488457146\
4805957721490319833611854945857872146747529277303318561488499356611945\
250675411612757010465356791，这个合数有 167 位，但是比较容易分解， 不到 1 秒钟就能分解出（这很奇怪，不知何故？），它有两个因子，一个是 4473297929，另一个是 2215707086722579688559276358532826248956997296824658187129019075996613\
8800400415156501827001797032745294740404832373351030284459396524271152\
620265237784647679。
至此，（6）已分解成功。剩下 （5），（7） 和（8a）未解决。

天山草

[这个贴子最后由天山草在 2013/09/26 05:55pm 第 6 次编辑]


（5）中有五个质因数：78087485383，955059211，4041943，679961，383，消去后得115803748393662249221904430519040355618527394268823242649175806830408102188348254509315050886227655112116740491407543143760599096075587645629094643688352623，这是一个 156 位的合数，需要分解。
这个数虽然不算太大，但是不容易分解，程序运行了 24 小时，还出不来，看来是难产。暂停吧。

天山草

[这个贴子最后由天山草在 2013/09/25 09:25am 第 3 次编辑]


再看看（7），它有因数 1542517，6802542547，198130021042483，116830056091194031，消去这四个因数后，（7）简化为：
370912034456759567748634291720394443847443520351105207569120594742088703357101600787581872531886411668400654227053780877448565678849668587414132638974144518884302869347535347299960352968451211421810920286843466139728228611749933359995587308408907127840748544241316041667362181933754799958972739401791724547436943393855278461743563733。
这是一个 333 位的合数，更是不好分解。

天山草

[这个贴子最后由天山草在 2013/09/25 09:26am 第 2 次编辑]


最后看看（8a），它有因数 27400114059743151607，消掉此因子得1749049828665828569965900513290864384659816929065798124173984444444455252231406496646534237036595300215845523431617121800187366728784852918899190782990677123479371412348903001578458902816086080145242076099748272116469830611655295531703617971781192838651480015963728809558033902380329223166043653883250819157096469412374764755518339188552068747712045644478161，这是个 358 位的合数。也不是省油的灯。

天山草

[这个贴子最后由天山草在 2013/09/25 09:33am 第 3 次编辑]


至此，共找到以下 18 个质因数：
3, 7, 11, 13, 37, 383, 679961, 1542517, 4041943, 955059211,
4473297929, 6802542547, 78087485383, 198130021042483, 116830056091194031, 27400114059743151607,112103021940812743353521,以及较大的一个质因数 2215707086722579688559276358532826248956997296824658187129019075996613\
8800400415156501827001797032745294740404832373351030284459396524271152\
620265237784647679。
以及 3 个“合数因数”：
a.115803748393662249221904430519040355618527394268823242649175806830408102188348254509315050886227655112116740491407543143760599096075587645629094643688352623。  此数有 156 位。
b.370912034456759567748634291720394443847443520351105207569120594742088703357101600787581872531886411668400654227053780877448565678849668587414132638974144518884302869347535347299960352968451211421810920286843466139728228611749933359995587308408907127840748544241316041667362181933754799958972739401791724547436943393855278461743563733。此数有 333 位。
c.1749049828665828569965900513290864384659816929065798124173984444444455252231406496646534237036595300215845523431617121800187366728784852918899190782990677123479371412348903001578458902816086080145242076099748272116469830611655295531703617971781192838651480015963728809558033902380329223166043653883250819157096469412374764755518339188552068747712045644478161。此数有 358 位。

elimqiu

下面引用由天山草在 2013/09/24 10:51am 发表的内容：
这样，令 x=10，原数的分子有以下因数（不一定是质因数，实际上只有 11 是质数，别的都是合数，需要进一步分解）构成：
（1）9；
（2）11；
（3）91；
...

天山草先生的解法很不错