请高手出个招，找出最小能使2^n-1被T整除的n值

海里游

我想完成下面的测试，请问那位高手有高招。 若有一个奇数T,在T-1的范围内，找出最小能使2^n-1被T整除的n值。 例1：若T=127， 当n=7时，2^n-1=2^7-1能被127整除，并且n=7是适合条件的最小数。 2、若T=129 当n=14时，2^n-1=2^14-1能被129整除，并且n=14是适合条件的最小数。

G-Spider

如果考虑计算的话， 因为mT+1=2^n 所以S=mT 有特点:二进制全1 比如1*127=127=1111111B 最高的一个bit 1在第6位，如果加1后，最高的bit 1进了一位，必满足条件了。

medie2005

请考虑φ(T)的素数分解. 其中φ(m)表示m的欧拉函数

海里游

有幸得到二位高人的指点！ 我虽然还没有实施，还不知是否会实施， 但G-Spider 所叙述的原理很明确，首先就抓住了数字特点， 高人的办法就是高。 medie2005所说考虑φ(T)的素数分解，是说G-Spider的方法要考虑素数分解？ 那要是弄个大数的话，就我这水平好像还很费劲呢。

G-Spider

大数的话，我的那方法不合适了。

海里游

噢，是这样，看来这也算是个难题了？ 很期盼谁还能出个高招进行大数计算。

wayne

6# 海里游 medie2005已经给出了一个充分的条件。 适合条件的最小数n一定是φ(T)的一个因子

wayne

6# 海里游 http://mathworld.wolfram.com/MultiplicativeOrder.html

1. Table[MultiplicativeOrder[2, m], {m, 1, 200, 2}]

复制代码

{1, 1} {3, 2} {5, 4} {7, 3} {9, 6} {11, 10} {13, 12} {15, 4} {17, 8} {19, 18} {21, 6} {23, 11} {25, 20} {27, 18} {29, 28} {31, 5} {33, 10} {35, 12} {37, 36} {39, 12} {41, 20} {43, 14} {45, 12} {47, 23} {49, 21} {51, 8} {53, 52} {55, 20} {57, 18} {59, 58} {61, 60} {63, 6} {65, 12} {67, 66} {69, 22} {71, 35} {73, 9} {75, 20} {77, 30} {79, 39} {81, 54} {83, 82} {85, 8} {87, 28} {89, 11} {91, 12} {93, 10} {95, 36} {97, 48} {99, 30} {101, 100} {103, 51} {105, 12} {107, 106} {109, 36} {111, 36} {113, 28} {115, 44} {117, 12} {119, 24} {121, 110} {123, 20} {125, 100} {127, 7} {129, 14} {131, 130} {133, 18} {135, 36} {137, 68} {139, 138} {141, 46} {143, 60} {145, 28} {147, 42} {149, 148} {151, 15} {153, 24} {155, 20} {157, 52} {159, 52} {161, 33} {163, 162} {165, 20} {167, 83} {169, 156} {171, 18} {173, 172} {175, 60} {177, 58} {179, 178} {181, 180} {183, 60} {185, 36} {187, 40} {189, 18} {191, 95} {193, 96} {195, 12} {197, 196} {199, 99}

海里游

wayne 是有点厉害，一串输出这么多。 不知大点的数字，不说百位，二十、三十位数好不好算， φ(T)中的因子不好找吧？ 要是用大数分解就麻烦了，如果能避开大数分解才好。

wayne

9# 海里游 这个题的瓶颈 本质上就是整数分解，基本上你能分解到多少位，MultiplicativeOrder 就能算到那个程度。 下面给出 T= 10^m + 1 对应的最小n，我就给到60位了， {m,n} {1, 10} {2, 100} {3, 60} {4, 612} {5, 9090} {6, 9900} {7, 909090} {8, 980392} {9, 525780} {10, 1374700} {11, 2721180} {12, 849915000} {13, 14551804410} {14, 1518743100} {15, 763560} {16, 10757824} {17, 9732271265340} {18, 249999750000} {19, 101010101010101010} {20, 4780769070063240} {21, 31839968160} {22, 63208567927959300} {23, 30238845147055380} {24, 76593124234068750000} {25, 5974852718019150} {26, 9501909883886661218900} {27, 3756429983879822340} {28, 68288031546290594763480} {29, 385208012326656394453004620} {30, 37935662427065700} {31, 303030303030303030303030303030} {32, 454107199791322539392480} {33, 228826728441270216180} {34, 11895652808643746807698218900} {35, 5153002783667850900678787170} {36, 5173492921847933277870000} {37, 46108552933314991444717835649220} {38, 310181394079257549159556944325200} {39, 30013459143267265148340} {40, 797844886761372155865976850078640} {41, 554323725055432372297807607214733880780} {42, 199276555277369253440323343700} {43, 20486093670634092262859405209421450} {44, 8678224560039944141728452762503328272796} {45, 54686290559837261467199400} {46, 23191849322887649440766047764754240100} {47, 5143427942724013651731444402859858728321690} {48, 3621541536749878611426273024} {49, 329619256378175885025051091403520301272270420} {50, 34366923271760553003541825541788709200} {51, 51397556652484487847690276271140201853860} {52, 14710058149341217727827514819180043874432195200} {53, 9090909090909090909090909090909090909090909090909090} {54, 2809083802657811953476980842571256750000} {55, 245029803115589300259923664313614006360} {56, 16869468857853983987603151693312452592953173200} {57, 15063654767078035614740718700194691642922899260} {58, 10541328481485126884562054116466687082819888197600} {59, 407843316386084059769879811253137130423484531182773720} {60, 39062476690894322522918480910567357083385000}