Problems & Puzzles: Puzzles

Puzzle 1116 A358527 G.L. Honaker, Jr. sent the following nice puzzle: It happens that the prime p is always of a prime factor of the integer 2^(p-1)-1. On November 20, 2022, G. L. Honaker submitted the OEIS sequence A358527 whose subject is "Position of p in the factorization (without multiplicity) of 2^(p-1)-1, where p is the n-th odd prime." The first members of this sequence are: 1, 2, 2, 2, 4, 3, 3, 2, 3, 4, 6, 6, 3, 2, 3, 2, 8, 4, 5, 8, 3, 2, 5, 6, 6, 3, 2, 8, 6, 6, 4, 4, 4, 3, 5, 7, 5, 2, 3, 2, 14, 4, 7, 7, 8, 9, 3, 2, 5, 5, 4, 12, 4, 4, 2, 3, 8, 7, 12, 3, 3, 6, 4, 10, 3, 9, 13, 2, 7, 7, 2, 3, 5, 8, 2, 3, 13, 10, 10, 4, 19, 4, 13, 3 Example: a(19) = 5 because the 19th odd prime is 71 and 71 is the 5th largest distinct prime factor of 2^(71-1)-1 = 1180591620717411303423 = 3 * 11 * 31 * 43 * 71 * 127 * 281 * 86171 * 122921. According to an email sent to me by G. L. Honaker, Jr., on November 27: Chuck Gaydos of Arizona computed the first 1000 terms of this sequence and the number 37 has yet to appear. Q1. Can you explain why p is always a prime factor of 2^(p-1)-1. Q2.  Can you compute the first 2^(p-1)-1 term with a prime p in the 37th position?

---

From 24-31 Dec. 2022, contributions came from Emmanuel Vantieghem, Giorgos Kalogeropoulos, Gennady Gusev, Adam Stinchcombe,
Oscar Volpatti, J-M Rebert, Alain Rochelli

***

Emmanuel wrote:

Q1. This is by Fermat's theorem.

Q2. The first term with  p  in the 37th position is when  p = 8737 = the 1089-th prime.

Since the table A358527 deals with odd primes only, we will find "37" at the position 1088.
 

We found :

-1 + 2^(8737-1) = (3^2)*5*(7^2)*(13^2)*17*29*43*53*79*97*113*127*157*193*241*257*313*337*449*547*673*911*(1093^2)*1249*
1429*1613*2017*2689*2731*3121*3361*4733*4993*5153*5419*8191*8737*F,
 

where  F = 181342436924105377724414518309563349632742450508703219358241190054978122826615697371929539616831946212
504196946003362235653320378375465945794935635303141391028715965206989952838288216968872682632550781193780728336
216035863573729607357517032679426218242731195512123902642819757785210123782675898029650543901245406747257068735
653422399103309631164742526837078033309551850392001278685646352337875504145993825799634319728624731443954604481
397595836760922367278080040417023844629194387315456968001002463960713641317705400549232605528058733457152052864
613002057343365611131352758786686313956586843906249603841855800268742197691307202576690294859757187585493073502
657735453352870451546116195061811359832019534873887815397414322916742997963183312904291748248327301942173024852
308018110768893554868656599974888211770043945246757028725857247462658749247207535749860226843347358466246893962
900769601049012015217370090428607905493402484302103988132861654768478141710786032865082034053917997510846327148
782368823648495502086695811919904027629861374953809605504009067910495181036278886734576787597174966498979964163
617616716733843327025378792813119545807373241954915816028627075158565896794836686745117420624283915249449342737
834589787701439596784506876763702948939200283207275004731704696550444821014046844910594991348067947437837465185
611490760318910041325732159123815618698256367288027790350592854519843178471900794901784021965553622604353747651
202534021601399079568110334642026033307372765653267400965596653170890671579394016757236412895382066966847296610
724188365619835946564661072976079404139730638723887278354747630116095940491912766775483076826101229186794580581
226422408752803224838335481928440011602111420477124262767189007771094252688895505431158804796454703714470399704
930630796440618599098083355210021092932187676640958631416498989109437488139431262583190931518381575423163488094
857634228832884268543868550795979951904167119643688653922821834761375235384871690868809696872907992418649386438
250597484541383877996996960978909163301510929572837707581839320926246140871701957364850716402481222102206096226
980235743318487503209385879710401238132923332947356198383254788538737738679590282877100226797523990445303989046
850519914664207154248198889887578000459431813001306614964073901993510532214173485455631520167926620328210621347
057279510224997749550149282731661849301270877238202851072369976613370519927189419679954900758053663712174782447
5857772081087312631401573473034968333933472637148953941415893521337585400462687324279130737858211  is an integer with no prime factor below 8737.

 

***

Giorgos wrote:

Q1.Fermat’s little theorem states that if p is a prime number, then for any integer a, the number a^p – a is an integer multiple of p.

a^p ≡ a (mod p). If a is not divisible by p then a^(p-1) ≡ 1 (mod p) and a^(p-1)-1 ≡ 0 (mod p).
 

So, for any odd prime p we have  2^(p-1)-1 ≡ 0 (mod p).

 

Q2, The first time that 37 appears in the sequence is at position 1088 for p = 8737.

The first 37 prime factors of 2^(8737-1)-1 are 

3,5,7,13,17,29,43,53,79,97,113,127,157,193,241,257,313,337,449,547,673,911,1093,1249,1429,1613,2017,2689,2731,3121,3361,4733,4993,
5153,5419,8191,8737...
 

 

Here are the positions of the first appearance of all integers from 1 to 100.

First we have the number, then the position of its first appearance in the sequence A358527 and third is the odd prime p 

#->n->p

1->1->3
2->2->5
3->6->17
4->5->13
5->19->71
6->11->37
7->36->157
8->17->61
9->46->211
10->64->313
11->208->1289
12->52->241
13->67->337
14->41->181
15->105->577
16->109->601
17->99->541
18->220->1381
19->81->421
20->196->1201
21->168->1009
22->256->1621
23->286->1873
24->480->3433
25->617->4561
26->278->1801
27->463->3301
28->325->2161
29->437->3061
30->700->5281
31->473->3361
32->368->2521
33->938->7393
34->840->6481
35->574->4201
36->623->4621
37->1088->8737
38->1137->9181
39->819->6301
40->2212->19501
41->959->7561
42->1923->16633
43->1462->12241
44->2948->26881
45->1818->15601
46->1145->9241
47->2360->21001
48->1675->14281
49->1504->12601
50->5456->53551
51->1765->15121
52->2716->24481
53->1899->16381
54->2449->21841
55->3962->37441
56->2880->26209
57->3062->28081
58->2116->18481
59->2833->25741
60->3893->36721
61->5692->56101
62->6193->61561
63->8460->87121
64->4949->48049
65->3269->30241
66->4898->47521
67->6632->66529
68->9773->102061
69->5556->54601
70->4706->45361
71->5268->51481
72->9259->96097
73->9302->96601
74->8806->91081
75->4479->42841
76->6957->70201
77->11543->122761
78->9339->97021
79->7762->79201
80->10125->106261
81->16121->177481
82->7793->79561
83->7706->78541
84->5628->55441
85->8007->81901
86->6541->65521
87->9038->93601
88->11198->118801
89->13105->141121
90->12106->129361
91->11514->122401
92->8926->92401
93->16145->177841
94->17432->193201
95->11818->126001
96->24622->282241
97->21383->241921
98->10207->107101
99->20779->234361
100->10522->110881

***

Gennady wrote:

Q1.

Fermat's little theorem states that if p is a prime number ...

So, if a = 2 and p is prime, then 2^(p-1) -1 is divisible by p.

 

Q2.   The first 2^(p-1)-1 term with a prime p in the 37th position is 1088 (p=8737).  The next terms are 1192, 15,31,1592, 1812.

***

Adam wrote:

(1) is a well known number theory result.  The group of non zero elements mod p, Zp*, form a multiplicative abelian group of order p-1.  The subgroup generated by 2 has order which divides the order of the group, so there is a smallest k such that 2^k=1 mod p, k divides p-1, and k is called the order of 2 mod p (write as order(2,p)).

 

(2) If p is a prime then 2^k=1 mod p iff order(2,p) divides k. Game plan: keep a running list of primes p and order of 2 mod p, for each new p, calculate order(2,p) and store that info and find those smaller primes q such that order(2,q) divides p-1.  Wait until p shows up as the 37th prime.  The first few primes I found were   8737,9661,12853,13441,15541

***

Oscar wrote:

About Q1, Fermat's little theorem explains the divisibility property.
If integer a is coprime with prime p, then p divides (a^(p-1))-1;
in particular, integer a = 2 is coprime with every odd prime p.
About Q2, I computed the first 200000 terms of sequence A358527, finding the least solution to equation a(n) = k for every k <= 204, and for 16 larger values up to k=270. The attached file P1116ov.txt contains 220 such triplets (k,n,p), where p is n-th odd prime.
The given example is the least solution to equation a(n) = 5, so the fifth entry is (5,19,71).
The 37-th entry is (37,1088,8737), because 8737 is the 1088-th odd prime and the least 37 prime factors of Mersenne integer M(8736) are:
3,5,7,13,17,29,43,53,79,97,113,127,157,193,241,257,313,337,449,547,673,911,1093,1249,1429,1613,2017,2689,2731,3121,3361,4733,4993,
5153,5419,8191,8737.
Last entry is visually nice: prime 2702701 is the 270-th factor of Mersenne integer M(2702700).

***

Jean-Marc wrote:

Q2.  Can you compute the first 2^(p-1)-1 term with a prime p in the 37th position?

 

I found 8737.

 

2^(8737-1) - 1  = [3, 2; 5, 1; 7, 2; 13, 2; 17, 1; 29, 1; 43, 1; 53, 1; 79, 1; 97, 1; 113, 1; 127, 1; 157, 1; 193, 1; 241, 1; 257, 1; 313, 1; 337, 1; 449,
 1; 547, 1; 673, 1; 911, 1; 1093, 2; 1249, 1; 1429, 1; 1613, 1; 2017, 1; 2689, 1; 2731, 1; 3121, 1; 3361, 1; 4733, 1; 4993, 1; 5153, 1; 5419, 1;
 8191, 1; 8737, 1;
18134243692410537772441451830956334963274245050870321935824119005497812282661569737192953961683194621250419
69460033622356533203783754659457949356353031413910287159652069899528382882169688726826325507811937807283362
16035863573729607357517032679426218242731195512123902642819757785210123782675898029650543901245406747257068
73565342239910330963116474252683707803330955185039200127868564635233787550414599382579963431972862473144395
46044813975958367609223672780800404170238446291943873154569680010024639607136413177054005492326055280587334
57152052864613002057343365611131352758786686313956586843906249603841855800268742197691307202576690294859757
18758549307350265773545335287045154611619506181135983201953487388781539741432291674299796318331290429174824
83273019421730248523080181107688935548686565999748882117700439452467570287258572474626587492472075357498602
26843347358466246893962900769601049012015217370090428607905493402484302103988132861654768478141710786032865
08203405391799751084632714878236882364849550208669581191990402762986137495380960550400906791049518103627888
67345767875971749664989799641636176167167338433270253787928131195458073732419549158160286270751585658967948
36686745117420624283915249449342737834589787701439596784506876763702948939200283207275004731704696550444821
01404684491059499134806794743783746518561149076031891004132573215912381561869825636728802779035059285451984
31784719007949017840219655536226043537476512025340216013990795681103346420260333073727656532674009655966531
70890671579394016757236412895382066966847296610724188365619835946564661072976079404139730638723887278354747
63011609594049191276677548307682610122918679458058122642240875280322483833548192844001160211142047712426276
71890077710942526888955054311588047964547037144703997049306307964406185990980833552100210929321876766409586
31416498989109437488139431262583190931518381575423163488094857634228832884268543868550795979951904167119643
68865392282183476137523538487169086880969687290799241864938643825059748454138387799699696097890916330151092
95728377075818393209262461408717019573648507164024812221022060962269802357433184875032093858797104012381329
23332947356198383254788538737738679590282877100226797523990445303989046850519914664207154248198889887578000
45943181300130661496407390199351053221417348545563152016792662032821062134705727951022499774955014928273166
18493012708772382028510723699766133705199271894196799549007580536637121747824475857772081087312631401573473
034968333933472637148953941415893521337585400462687324279130737858211, 1]

 

***

Alain wrote:

Q1 : p is always a prime factor of 2^(p-1)-1 is the consequence of Fermat's Little Theorem.

It is easy to show that 3 is always a prime factor of 2^(p-1)-1.

Q2 : It is true that the first 1000 terms of this sequence A358527 do not contain the number 37.

The number 37 appears for the first time at the 1088th term corresponding to p equal to 8737.

Then it is at the 1192th term corresponding to p equal to 9661.

 

***