最大素因子

白新岭

奉尚打油诗一首
等待朋友给个冠名（诗的主题）

提笔如有神，往事怎能分（何时分）。
喝酒开八卦，不是圣上人！

yangchuanju

2是一个最小的素数，
2^2-1=3，3是第2个素数，
2^3-1=7，7是第4个素数，
2^7-1=127，127也是一个素数，
2^127=170141183460469231731687303715884105727，已知它是一个38位的素数，
2^170141183460469231731687303715884105727-1=?  它还是素数吗？
有不少人揣测它是素数，若如此这个素数将达到5.12175997193696*10^37位.

太阳先生！
您不是一直想找几个亿位大素数吗？
请验证一下它是不是素数？
它可是50万亿亿亿亿位的大素数呀！
太阳先生如能检验成立，那您就是世界名人啦！

yangchuanju

如果觉得2^(2^127-1)-1太大，那就检验一下2^(2^31-1)-1吧！
2^5-1=31，31是一个素数；
2^31-1=2147483647，它是一个10位素数；
2^2147483647-1很有可能也是一个素数；
请太阳先生检验一下这个较小点的数字吧！
它有6亿多位呢！

yangchuanju

太阳先生应该明晰，梅森数2^p-1之中含有许多大素数，或者本身就是素数；(2^3p-1)/(2^p-1)=2^2p+2^p+1之中也含有许多大素数；
然而2^2p+2^p+1之中的最大素数有不少大于2^p-1的，但不一定全都大于2^p-1。
式中p是素数，下面的q是另一个素数。

同样，2^pq-1=(2^p-1)*[2^(pq-p)+2^(pq-2p)+……+2^p+1]=(2^q-1)*[2^(pq-q)+2^(pq-2q)+……+2^q+1]，
(2^pq-1)/[(2^p-1)*(2^q-1)]之中含有许多大素数；
然而这些大素数一般都大于2^p-1或2^q-1，但不一定全都大于2^p-1或2^q-1。

例：2^11-1=2047=23*89
2^22-1=4194303=3*23*89*683，分解式中的23*89来自2^11-1，3来自2^2-1，683是余因子，最大素因子；
2^33-1=8589934591<10>=7×23×89×599479，分解式中的23*89来自2^11-1，7来自2^3-1，599479是余因子，最大素因子；
2^55-1=36028797018963967<17>=23*31*89*881*3191*201961，分解式中的23*89来自2^11-1，31来自2^5-1，881*3191*201961是复合余因子；
2^77-1=151115727451828646838271<24>=23*89*127*581283643249112959<18>，分解式中的23*89来自2^11-1，127来自2^7-1，581283643249112959<18>是余因子，最大素因子；
2^121-1=2658455991569831745807614120560689151<37>=
23*89*727*1786393878363164227858270210279<31>，分解式中的23*89来自2^11-1，只有一个23*89，727*1786393878363164227858270210279<31>是复合余因子。


又例：2^11-1=2047=23*89
2^23-1=8388607=47*178481
2^89-1=618970019642690137449562111<27>=618970019642690137449562111<27>素数
2^2047-1=
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650498045875098875194826053398028819192033784138396109321309878080919047169238085235290822926018152521443787945770532904303776199561965192760957166694834171210342487393282284747428088017663161029038902829665513096354230157075129296432088558362971801859230928678799175576150822952201848806616643615613562842355410104862578550863465661734839271290328348967522998634176499319107762583194718667771801067716614802322659239302476074096777926805529798115327
2^2047-1<617>=
47*131009*178481*724639*2529391927<10>*70676429054711<14>*618970019642690137449562111<27>*1833699215...33<549>合数
(2^2047-1)/(2^23-1)/(2^89-1)=131009*724639*2529391927<10>*70676429054711<14>*1833699215...33<549>合数
这个余因子尚未完全分解，549位的复合因子之中可能有（或者一定有）大于27位的素因子。

yangchuanju

2^3-1=7
2^9-1=511=7*73，余因子73；
2^27-1= 134217727=7*73*262657，余因子262657；
2^81-1=2417851639229258349412351<25>=7*73*2593*71119*262657*97685839，
余因子2593*71119*97685839；
2^243-1<74>=
7*73*487*2593*71119*262657*97685839*16753783618801<14>*192971705688577<15>*3712990163251158343<19>，
余因子487*16753783618801<14>*192971705688577<15>*3712990163251158343<19>；
2^729-1<220>=
7*73*487*2593*71119*80191*97687*262657*379081*97685839*16753783618801<14>*192971705688577<15>*3712990163251158343<19>*664728004346558283448724389870269691211809<42>*1012137457...61<90>，
余因子80191*97687*379081*664728004346558283448724389870269691211809<42>*1012137457...61<90>

2^2187-1<659>=
7*73*487*2593*39367*71119*80191*97687*262657*379081*97685839*7606246033<10>*263196614521<12>*529063556041<12>*16753783618801<14>*192971705688577<15>*3712990163251158343<19>*664728004346558283448724389870269691211809<42>*1012137457...61<90>*1912682319...67<402>合数
2^6561-1<1976>=
7*73*487*2593*39367*71119*80191*97687*209953*262657*379081*1299079*97685839*7606246033<10>*263196614521<12>*529063556041<12>*16753783618801<14>*192971705688577<15>*3712990163251158343<19>*70063267397606709277393<23>*664728004346558283448724389870269691211809<42>*1012137457...61<90>*1912682319...67<402>合数*2654318295...43<1283>合数
2^19683-1<5926>=
7*73*487*2593*39367*71119*80191*97687*209953*262657*379081*1299079*97685839*141560137*7606246033<10>*263196614521<12>*529063556041<12>*16753783618801<14>*192971705688577<15>*58669629894216721<17>*3712990163251158343<19>*70063267397606709277393<23>*291672371750729982059791572512470687<36>*664728004346558283448724389870269691211809<42>*1012137457...61<90>*1912682319...67<402>合数*2654318295...43<1283>合数*5387080766...43<3890>合数
2^59049-1<17776>=
7*73*487*2593*39367*71119*80191*97687*209953*262657*379081*472393*1299079*97685839*141560137*7606246033<10>*40518479017<11>*68021967943<11>*263196614521<12>*529063556041<12>*16753783618801<14>*166503590645473<15>*192971705688577<15>*58669629894216721<17>*3712990163251158343<19>*70063267397606709277393<23>*291672371750729982059791572512470687<36>*664728004346558283448724389870269691211809<42>*1012137457...61<90>*1912682319...67<402>合数*2654318295...43<1283>合数*5387080766...43<3890>合数*1025132316...47<11810>合数
2^177147-1<53327>=
7*73*487*2593*39367*71119*80191*97687*209953*262657*379081*472393*1299079*97685839*141560137*7606246033<10>*40518479017<11>*68021967943<11>*263196614521<12>*529063556041<12>*16753783618801<14>*166503590645473<15>*192971705688577<15>*58669629894216721<17>*3712990163251158343<19>*10939874335459407703<20>*70063267397606709277393<23>*291672371750729982059791572512470687<36>*664728004346558283448724389870269691211809<42>*1012137457...61<90>*1912682319...67<402>合数*2654318295...43<1283>合数*5387080766...43<3890>合数*1025132316...47<11810>合数*1003264837...19<35533>合数
2^531441-1<159980>=
7*73*487*2593*39367*71119*80191*97687*209953*262657*379081*472393*1299079*88219207*97685839*141560137*7606246033<10>*40518479017<11>*68021967943<11>*263196614521<12>*529063556041<12>*16753783618801<14>*166503590645473<15>*192971705688577<15>*58669629894216721<17>*3712990163251158343<19>*10939874335459407703<20>*70063267397606709277393<23>*291672371750729982059791572512470687<36>*664728004346558283448724389870269691211809<42>*1012137457...61<90>*1912682319...67<402>合数*2654318295...43<1283>合数*5387080766...43<3890>合数*1025132316...47<11810>合数*1003264837...19<35533>合数*1498720421...59<106646>合数
……