All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Truth or consequences (Posted on 2017-11-02) Difficulty: 4 of 5
Is it true that 2n-2 is not divisible by n when n is composite?

Prove or show a counterexample.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 1 of 2
The first twenty counterexamples follow. The first line shows n and 2^n-2. The second line shows a partial prime factorization of 2^n-2, up to the limit of UBASIC to show the smallest prime factor; that line terminates with the zero that UBASIC returns when asked for the smallest prime factor. The third line shows the prime factorization of n; you can verify that both are found in the prime factorization of 2^n-2 and so n divides the latter.

341   4479489484355608421114884561136888556243290994469299069799978201927583742360321890761754986543214231550 
2  3  5  5  11  31  41  137  953  1021  4421  26317  43691  131071  0 
11  31 

561   7547924849643082704483109161976537781833842440832880856752412600491248324784297704172253450355317535082
936750061527689799541169259849585265122868502865392087298790653950 
2  3  5  5  11  17  29  31  41  43  71  113  127  257  281  4481  5153  61681  86171  122921  0 
3  11  17 

645   1459980997639102469965174913824093223965833122319539177785341605727768053506776763681892099621558847929
16553906355021033942038551084014015944085162231110854024063829579528478402651974151891320830 
2  3  5  29  43  47  113  127  277  1013  1289  1657  1933  3221  30269  0 
3  5  43 

1105   4346555292958034717687524570749653691531180310181582559195262943129001896813573915905725466626419389535
5450441452311627120123921738351775907697754696962011910034443198100449061705165261326978338453878913683
9141648409549944708158609707369153030498572184824311434246367523036288130211715938692732013989877070958
884766361297687813292030 
2  3  3  5  7  13  17  47  97  139  241  257  277  673  1013  1657  30269  0 
5  13  17 

1387   3377567102387465838194817161483750504129906689048778555046527505938063359016262072445429458606977698392
2604409382323356772321222379124276373506628639468599772852873341345764335918187208933167964648215763223
2685245779204592582583720865005182483748138387864910801497727526074455162280958555659532993239599677287
8892085054615906956473475981984212998293287300759245897824701939629900799635710532421572511136301508909
334526 
2  3  3  3  7  7  19  23  43  67  73  89  127  199  337  463  617  683  5347  5419  14323  20857  78233  92737  0 
19  73 

1729   3025955263570019164018502277869853398058543745963126397283707470775892712704232437030043920740033026198
8472164262649512891884983076335911224711118741639261573749898146108785742255065717130085209408458055585
7942985570738231419687525783564788285621871741725085612510228468354691202070954415518824737971685957295
0811281937944702307676679453365814328593305957854274867553594143460475201489987084725797475032257007739
9294677581910523695792606813529078759274589264848923154827578713239056475245050253159810279037690534441
254910 
2  3  3  3  3  5  7  13  17  19  37  73  97  109  193  241  257  433  577  641  673  1153  3457  6337  38737  65537  87211  0 
7  13  19 

1905   289828934267544987199309886767227081270423799544327138497317371614334613912036236191118735987308059741
738735499230895689029171071008479978253640864507810455557212715418799431696615523973503892043629789223
935765936515689111883909184854967608381524386496427622902865872397141897639941794017917488279391809026
954011527751683093838667953583411106743560564412253848474449006823842441569352783685838143207620565199
159486690553057238560202205875741616759208029215285633279486899233728727695571472160111511138938580504
2750809829647183709050415792984430793780239805560442788125868030 
2  3  5  17  17  29  43  113  127  137  239  257  953  2381  5153  9521  20231  26317  42841  43691  131071  0 
3  5  127 

2047   161585030356555036503574383443349759802220513348577420160651727137623275694339454465986007057614567318
443589804609490097470597795752454605475440761932241415603154386836504980458750988751948260533980288191
920337841383961093213098780809190471692380852352908229260181525214437879457705329043037761995619651927
609571666948341712103424873932822847474280880176631610290389028296655130963542301570751292964320885583
629718018592309286787991755761508229522018488066166436156135628423554101048625785508634656617348392712
903283489675229986341764993191077625831947186677718010677166148023226592393024760740967779268055297981
15326 
2  3  3  7  23  67  89  683  20857  0 
23  89 

2465   109380350755178719899664405667102693366974287130654171649519074644844420690304165629126575587043435177
097113846546870702967637885406036443790626744439586833021805517874959787047329712798408911281903777594
917215226605694401304212975074158479442765810852286777617352214124293809990111776101048351138405133686
253272725038599124813501233765520631615133280099205134367742048495864218403732925182567033012277129428
074027747248545033274708028206207097517724193978023412459788839809516963542329624097824050111067908008
753366492311160683247991551907127832381618427447849396133635438090401539831158961073924032181324598105
895188068970519331851204718020008157962744521750797140038308573388415170504822264851231703422389936836
40328922712936536884465631230 
2  3  5  17  23  29  43  89  113  127  257  353  397  449  617  683  2113  2689  5153  8317  13553  29569  65537  78233  110881  0 
5  17  29 

2701   120786469797636034401347591330177580066689876142136337158518164126647387980459737585662974737773971518
791814014477162052813030182396079179590275096336820196586360490486767194944165115930829181173622433047
194083492811001023500226762940995216154955246908866800745247317761539596599117252954819055972685227419
443535214220925342184293152243061522001076427410077129730664133205533898932517249884674455168604599201
113193259309957775423794472173510341636160412750417525217096421131610927868343732594570136759727606257
047349259289528472429469841166652513685910429594808948663152238847087775373175097321165674774550841030
929984930127413628055154462938308071919882933305599642590405943674363625581277480281303057333309296421
1019020063887968801900020564432803975656023907016926277174895455665608875835821206908658782675402750 
2  3  3  3  3  5  5  5  7  11  13  19  31  37  41  61  73  101  109  151  181  251  271  331  541  601  631  811  1201  1321  1801  4051  8101  15121  23311  30241  49681  54001  63901  87211  100801  115201  0 
37  73 

2821   160552757167047019123235099792089121234320031948882412981607526073099330677528932193222273442050800600
083608725577734647068829901753042666581731222653191367136823050503798457495420833485514890917331292451
616566109369917889388396129439027653513241306815253097572738510437371484483822746576512039580471785834
044879854513179379850597383194714023418545055428426372130673701689117778217731333014878453166201303526
080837063915791853906957028713993709216877231113453752929457193246251965890566354909446082751029085967
067366028802610449234049983751255817977664450527331471161608866519848992783379209102500150910933249918
074412373343150576850796519958616924001717627076049724309770124767961296459358374257789500950311100520
380895905954317886355341121611683319890213751110273251182221580821453929244277229281563883883354919439
2361008812930656758841050138673150 
2  3  3  5  5  7  11  13  31  41  61  151  283  331  941  1129  1321  2351  3761  4513  5641  16921  29611  0 
7  13  31 

3277   298741660675683357549586509889549200949011813922209471399239638498197244651973332607205347797580981919
820265560948145795923493426693923976691020954520305882568748771091147069115359832006334009535702693826
873183840083097066430322016881041747387098038785780607512797370921424910776699469954614889495825425014
029704993861465976948779580899226163757925213107145101741165302415736547643223957058974928358474738812
414420976409442934975054082888894539099390224303702061595940733080672935220096357478410920687548341860
080802345011223279963557958722387789967501540045168022192993334441242852235823891721212597981532890181
349381548089557665316013220803241517988460879570245837167286919013898906591622267272903537103332297513
432885774511415184005760948650564425193343029009030242596043945096602788200503431121295236344474587920
456308237502250532159577940286508167982760584790824505742720730253060551276971174319485735644843729854
372449644790340275201791182402460047587796357140816213280701674422270 
2  3  3  3  5  7  7  13  13  19  29  37  43  53  73  79  109  113  127  157  313  337  547  911  937  1093  1093  1249  1429  1613  2731  3121  4733  5419  6553  7489  8191  11467  14449  21061  21841  86113  92737  121369  0 
29  113 

4033   113232869414784580987661217372686583827828414534659242977219008154886185996520939651014673713621655822
522737415516357619174296865264074848322129351001746766974165160347217317677233002256099625428435302656
566049660146824769779630865195811855203917902629087874160686170128221986624669446099094875463541559646
101521279760851000330409979963994426799742322175323002624440450275009032345647835476422600599614763515
637969600547713590423241993497008726285380872552125226603568889625827341001205436735593050290854614600
567731903607997616131278058341406044898936380639861014681977355046132169443278850990305104250263222165
982769489393045416394612406373139857384549056173116403606415276041777382242530868394587814436768191041
121111793894301888266111726795231296822224941509312221497622475306749576955432145105177219232752861788
192962729002589311309646285097646519504431432586703998839435124612354129859264101378030028811157388817
228707080361298820217811047096382710848110544362285680354974592379528044600771869768967964683803316368
852665249553944171811587030919201240136367250362655927272989599164933661062517322651535593484284707060
960576349647472582144955367441181942579285574396460162728603736785821351743077217508463214590 
2  3  3  3  5  7  7  13  17  19  29  37  43  73  97  109  113  127  193  241  257  337  433  449  577  641  673  1009  1153  1429  2017  2689  3361  3457  5153  5419  6337  14449  21169  34273  38737  65537  92737  0 
37  109 

4369   158507952445918539553273188870232695183528769747151537349986991977271122639448294109307020241816845307
211433178049636737382499172586176292104457997205185110888404070016172908283037952257321095919421586470
370913355263055289028918584280696464653417567742051184145377805349795208938230842814688311639512598519
683459996384650584121556276317474886399567267460762418363159384098030378899150538494195328010531913818
050176833366166951802232157227318977381700783319240157361213017381871330852783354635510339761664333992
948553953881594772545519999749386198906332284884819719412886755119073479874324219878952575986375928925
000974120382007136337374366145614364236405565182300056331792451982422163678046620353749504378066457407
903772581720273228869444214648016481080564129033727381645945178253110922906245466208439106101252170261
751329945674454756914655829840386115692670760566409340256402677540339270957105361635611554786883561440
465522342824326264395903792243515526809184251576562206128334880821889383701013791082568473445238339330
108417958702743389972848823818204631188449712979773726327467168285073988730933674319641009854069917426
674587705241096553796613253062752272121454497463221744563766910538111469778507519215675107727185678557
07526451986025818030719892107073333567739906446377840148793786175404882428192527595404787710 
2  3  3  5  7  7  13  13  17  29  43  53  79  97  113  127  157  241  257  313  337  547  673  911  1093  1093  1249  1429  1613  2017  2731  3121  3361  4733  4993  5153  5419  8191  8737  14449  21841  26209  94849  121369  0 
17  257 

4371   634031809783674158213092755480930780734115078988606149399947967909084490557793176437228080967267381228
845732712198546949529996690344705168417831988820740443553616280064691633132151809029284383677686345881
483653421052221156115674337122785858613670270968204736581511221399180835752923371258753246558050394078
733839985538602336486225105269899545598269069843049673452637536392121515596602153976781312042127655272
200707333464667807208928628909275909526803133276960629444852069527485323411133418542041359046657335971
794215815526379090182079998997544795625329139539278877651547020476293919497296879515810303945503715700
003896481528028545349497464582457456945622260729200225327169807929688654712186481414998017512265829631
615090326881092915477776858592065924322256516134909526583780713012443691624981864833756424405008681047
005319782697819027658623319361544462770683042265637361025610710161357083828421446542446219147534245761
862089371297305057583615168974062107236737006306248824513339523287557534804055164330273893780953357320
433671834810973559891395295272818524753798851919094905309868673140295954923734697278564039416279669706
698350820964386215186453012251009088485817989852886978255067642152445879114030076862700430908742714228
30105807944103272122879568428293334270959625785511360595175144701619529712770110381619150846 
2  3  11  31  47  191  691  2281  7867  14951  34961  0 
3  31  47

4681   132254270122988324491860643703858344853876854759077491230003149814820112429917865483748336819112783721
778507445552835965432773216181306301735272046560158726116645208331405363676316945940427051966801458088
347599968288893602691736131883316475958191048025844494034519563396449652883069351833551884157154155575
472773705362816296582701839437829978470904747483781438011655008904320121169197522045518779844158808616
036820721661305057235453595315520086125948819595492323210783296398491430373454293662686564150325427851
286674600682423645799468695653581239412469994899186784208319355310787895084951719818189214741769344009
410890676888099118889579678820462621291480547127919382445307386665096021897400480427119005471311015643
332172403122543045369175826303760544719406320426204849671511102879390589373731384869331527831496674099
945344951863471729109371594522763162175727543870848501130101537553917905051455725675478544195664976607
764030126221724931665128452104501019130604489731414375540856240974648790476522172830409732978599917319
334838608259413539857325185965417890099397850767946423569841119225606238346606070519542588969629793464
026362755778167257091575672970737853243592310674876834633720121301451836945881747080113421507784390715
778573447854119916482408620254551911171018931792591177811306091620943936504704627118476841808514907359
394986257048592696104613727866783441077556272915884079543120939057907286908287844350 
2  3  3  3  5  5  7  11  13  13  17  19  31  37  41  53  61  73  79  109  131  151  157  181  241  313  331  433  521  631  937  1171  1249  1321  1613  1873  2341  2731  3121  6553  7489  8191  11701  21061  21841  23311  38737  42641  51481  54001  61681  65521  86113  107251  121369  0 
31  151 


    4   kill "truconsq.txt"
    5   open "truconsq.txt" for output as #2
   10   for N=4 to 5000
   20     if prmdiv(N)<N then
   30       :if (2^N-2)@N=0 then print N:Ct=Ct+1
   31         :print #2,N,2^N-2
   40         :V=2^N-2
   50         :while V>1:print prmdiv(V);:print #2,prmdiv(v);:if prmdiv(v)=0 then ?v:goto 80:endif
   60         :V=V\prmdiv(V)
   70         :wend
   80         :print:print #2
   90         :V=n
  100         :while V>1:print prmdiv(V);:print #2,prmdiv(v);:if prmdiv(v)=0 then ?v:goto 130:endif
  110         :V=V\prmdiv(V)
  120         :wend
  130         :print:print #2
  176     if Ct>19 then cancel for:goto 50
  180   next
  190   close #2
  900   end


  Posted by Charlie on 2017-11-02 17:51:44
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information