【趣题征解】求一个正整数 n，使得 3^n ≡ 2  mod （n）

guanchunhe

如果天山草先生所得到就是这个解，那么以后可能就是无解。
如果天山草先生所得到不是这个解，那么以后应该还会有其它的解。不过其计算难度得非常大。如

天山草

[这个贴子最后由天山草在 2011/09/06 09:37pm 第 1 次编辑]

如果天山草先生所得到就是这个解，那么以后可能就是无解。
如果天山草先生所得到不是这个解，那么以后应该还会有其它的解。不过其计算难度得非常大。
----------------------------------------------------
当然不是 k=1，n=1 这样的“特解”了。况且这个“特解”也不正确。

天山草

天山草

3^2929 的值等于下面这个大数，请能验算的网友进行检验：
3077195395308515263665868726119680782619925222989769810263863059676959\
0341159030692006382121517666879726583415818164993481266306917336487242\
5882467063663450898967125915936572172815069556524745965197026484581599\
9454893455781801390302887303468939489330053738287074470895154895896455\
1135230433977968213406901746504378400794212559542242295397178737610867\
5857586057663099221057527047809633467457740291936971165224134927282618\
0711834553036389044851072880020552786523816639254009692211494330957424\
0205316470702029181230186159486956388583482039397641239945119301749302\
2168464247000820571932302263390656898066603599757459829895906691827810\
5950209788757933361470802099724717567998839413031917639022467590911801\
8342477973769391938512667679738119988255537568247136257290168323731956\
2731996746230262231755041376196945731582943018633355591477877706874502\
0578080664227245494005557955288383500779159167531895847850377628409072\
2567318766215911778982717939709783367298385940620749432939540102241664\
5593090949242954631017523910832582444324000097989557821163359064288808\
5893966058891965700645834573685018695828222068539288375532635596372944\
5325236353030718433697206599494944232528052414835685994391823138265083\
3890344027965107044254172447257355987806694771592557264252928950289425\
9624867674842721538273988382960434851418311325319149858760059532535788\
08262355916851833090483230020604614843212536331459364833870957218883。

天山草

本人是用 mathematica 软件“硬算”找出解答的。程序如下，有了解这个软件的朋友，若有兴趣的话，可以接着在 4500000 以后寻找，看能不能发现别的“金豆豆”。

天山草

[这个贴子最后由天山草在 2011/09/07 09:38am 第 1 次编辑]

用 mathematica 验证的结果：

任在深

很好哇！
太好了！

awei

[这个贴子最后由awei在 2011/09/07 00:07pm 第 1 次编辑]

3^2929=F1=F2×2929+2 F1=307719539530851526366586872611968078261992522298976981026386305967695903411590306920063821215176668797265834158181649934812663069173364872425882467063663450898967125915936572172815069556524745965197026484581599945489345578180139030288730346893948933005373828707447089515489589645511352304339779682134069017465043784007942125595422422953971787376108675857586057663099221057527047809633467457740291936971165224134927282618071183455303638904485107288002055278652381663925400969221149433095742402053164707020291812301861594869563885834820393976412399451193017493022168464247000820571932302263390656898066603599757459829895906691827810595020978875793336147080209972471756799883941303191763902246759091180183424779737693919385126676797381199882555375682471362572901683237319562731996746230262231755041376196945731582943018633355591477877706874502057808066422724549400555795528838350077915916753189584785037762840907225673187662159117789827179397097833672983859406207494329395401022416645593090949242954631017523910832582444324000097989557821163359064288808589396605889196570064583457368501869582822206853928837553263559637294453252363530307184336972065994949442325280524148356859943918231382650833890344027965107044254172447257355987806694771592557264252928950289425962486767484272153827398838296043485141831132531914985876005953253578808262355916851833090483230020604614843212536331459364833870957218883
    F2=105059590143684372265820031618971689403206733458168993180739605997847696623963914960759242477014909114805679125360754501472401184422453012094872812244337129019790756543508559977062160995740780459268360015220757919252081112386527494123841019765772937181759586448428504443663226236091277673041918635074793109411076744284036232705845825522011535464700811149739179809866582812402542782394492133062578332868270817389869335137613924020247060056157428230796195042216586433569614533704728382757167088444235133841000960157685761307464624730222053252445339519014345337324058881613861666292909628632089674598179106725762191816284024135140939090140313716556277277937934439218762990742212804094149505717568825940656683093116317486987069537998423079509237069198522144954899857711614736337315379388959450923537513211657812080212706942081116926554355368556523662706187341942437881801136510191218134488478384972613532865428783620919490495786656807725223419971947310680730422057867644040765115198581629597456211319437015201062080089602022533321266492939967005484564291085488769508090327778963283498976397945654560209603563521086910084429652868679935236321043691384771235726297466891139759938526431625600085638064303184692764439827303669258230108503480632158606099096254336049650379817947246252015646090419356791903428416228245788660251282332964690613950957977757539464145862076000209915743440195103914248504935889
[color=#0000FF]不会有第二个了吧？呵呵！

guanchunhe

假设  3^2929≡ 2  (mod 2929)
因为  2929=29*101
那么就应该满足    3^2929≡ 2  (mod 29)    且   3^2929≡ 2  (mod 101)
但事实是     3^2929≡ -2  (mod 101)
所以，这个解不成立。

awei

[这个贴子最后由awei在 2011/09/08 09:36am 第 6 次编辑]

[color=#0000FF]
用mathematica计算 也是3^2929≡ 2  (mod 101)
设3^2929=2929k+2  
3^2929≡2929k+2 (mod 101)
因为2929≡0 (mod 101)
所以3^2929≡2 (mod 101)
楼上的理解错误。
计算机找这样的数太慢了，楼主也真有耐性，呵呵！
3^2929有这几个特点：
①φ（2929）=(101-1)*(29-1)=2800
小于2929并且与2929不互质的数有2^7+1个
②φ（3^2929）=（3-1）*3^(2929-1)=2*3^2928
③2929=101*29，所以2929没有原根。
④3^2929的原根数=φ（φ（3^2929））=φ（2*3^2928）=2*3^2927
希望能找到第二个，不好找吧？