20220417, 20:15  #1 
"James Short"
Mar 2019
Canada
10010_{2} Posts 
factoring composite mersennes
Suppose is composite for prime and define the iteration function with . Does there exist some integer such that for all , we have ?

20220422, 11:41  #2  
"Καλός"
May 2018
5·73 Posts 
Quote:
Code:
p = 1277; Mn = 2^p  1; xn = 3; While[(GCD[xn  1, Mn] == 1) && (xn != 0), xn = Mod[(xn^(12*p*5)  1)*(xn^(12*p*7)  1) + 1, Mn];]; Print[xn]; 

20220422, 15:11  #3 
Feb 2017
Nowhere
13·461 Posts 
I think you mean
where x_{0} is Mod(3,2^p  1). I am not certain, but I suspect the answer is "yes." A prime factor q of 2^p  1 divides the gcd of (the lift of) x_{n+1}  1 and 2^p  1 when x_{n+1} is 1 (mod q). When that happens, all further x's will also be 1 (mod q), so q will divide the gcd forever after. So if the gcd becomes greater than 1 at some point, it stays greater than 1 after that point. We know that q = 2*k*p + 1. If 2*k divides either 60 or 84, x^{60p} or x^{84p} will automatically be 1 (mod q) [assuming x is not 0 (mod q).] In fact, we know that for p > 2, q == 1 or 7 (mod 8), which means k would have to divide 15 or 21; k = 1, 3, 5, 7, 15, or 21. If q = 2*k*p + 1 happens to be a factor of M_{p} for one of these k, it will divide the first gcd. However, trial factoring would almost certainly be faster. In addition, if x_{n} happens to hit one of the values 2, 4, ..., 2^p1 (mod 2^p  1), then x_{n+1} will be 1 (mod 2^p  1) whether this is prime or composite. For example with p = 7, x_{1} = Mod(4,127) so x_{2} and all further x's will be 1 (mod 127). The recursion is unmotivated at this point, and the iterations are expensive to compute. EDIT: My suspicion was wrong. The answer to your question is "no." The first prime Mersenne number for which the gcd remains 1 forever is for p = 17. After a while, the iteration cycles through 13 values. Code:
? p=17;a=2^p1;m=Mod(3,a);v=vector(100);for(i=1,100,m=(m^(60*p)1)*(m^(84*p)1)+1;v[i]=lift(m);g=gcd(lift(m)1,a);if(g>1,print(c" "g))) ? for(i=1,#v1,for(j=i+1,#v,if(v[i]==v[j],print(i" "j);break(2)))) 20 33 ? for(i=20,33,print(i" "v[i])) 20 87019 21 21750 22 15865 23 46346 24 89767 25 85845 26 68218 27 113345 28 47439 29 35712 30 26871 31 12601 32 121150 33 87019 ? Code:
? p=41;a=2^p1;m=Mod(3,a);v=vector(1000);for(i=1,1000,m=(m^(60*p)1)*(m^(84*p)1)+1;v[i]=lift(m);g=gcd(lift(m)1,a);if(g>1,print(c" "g))) ? for(i=1,#v1,for(j=i+1,#v,if(v[i]==v[j],print(i" "j);break(2)))) 655 665 ? for(i=655,666,print(i" "v[i])) 655 1070040474851 656 2109318288198 657 1990816244601 658 70809791609 659 509766907190 660 1942949745660 661 673267198969 662 396358531829 663 1458749118825 664 434250274170 665 1070040474851 666 2109318288198 ? print(factor(2^411)) [13367, 1; 164511353, 1] ? Last fiddled with by Dr Sardonicus on 20220423 at 13:40 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Doing P1 on known composite Mersennes  bur  Factoring  14  20210426 18:06 
Composite integers n satisfying prime exponents of Mersennes  carpetpool  carpetpool  7  20170105 04:36 
Factoring nonform composite  roger  Factoring  15  20061129 08:58 
Factoring with Highly Composite Modulus  mgb  Math  3  20060909 10:35 
Factoring Double mersennes  Citrix  Miscellaneous Math  2  20051004 08:08 