20220808, 12:10  #34 
Mar 2021
France
41 Posts 
Ok thanks for your answer I understand a little more now.
Do you think you can prove the same thing about Wagstaff composite numbers ? I found than if 8p+1 = 256a^2+(2*b1)^2 and p and 8p+1 is prime, then 8p+1 divides (2^p+1)/3. Code:
cnt=0; for(b=1, 1000, for(a=1, 1000, q=256*(a)^2+(2*b1)^2; p=(q1)/8; if(isprime(p)&&isprime(q), cnt++; print(cnt": "q", "p)))) 
20220808, 14:32  #35  
Feb 2017
Nowhere
13·461 Posts 
Quote:
An even older result is the criterion for when 2 is a biquadratic (fourth power) residue (mod q); namely, when q = x^2 + 64*y^2 (x, y positive integers). As already indicated, however, it is much, much quicker to determine whether q = 8*p + 1 divides 2^p  1 by modulo arithmetic, than it is to determine whether q is of the appropriate quadratic form. I would expect that q = 8*p + 1 divides 2^p  1 for about a quarter of the primes p for which q = 8*p + 1 is prime. Unfortunately, which quarter is not predictable using linear congruences. I don't necessarily trust my thinking here, so someone may want to check on the proportion... EDIT: I checked it myself for p < 10^{8}, with the results following: Code:
? c1=0;c2=0;forprime(p=3,100000000,q=8*p+1;if(ispseudoprime(q),c1++;if(Mod(2,q)^p1==0,c2++)));print(c1" "c2" "1.*c2/c1) 392989 98264 0.25004262205812376427838947146103326047 Last fiddled with by Dr Sardonicus on 20220808 at 23:02 Reason: As indicated 

20220809, 01:39  #36 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2^{4}×3×211 Posts 

20220809, 13:17  #37 
Feb 2017
Nowhere
13551_{8} Posts 
Reread the explanatory post by charybdis. Also note the result I mentioned about when 2 is a fourth power residue (mod q). The result you state is an easy consequence of your hypothesis and those results.

20220811, 11:10  #38 
"Καλός"
May 2018
5×73 Posts 
A repetitive pattern in observed after k = 12 for the primes p and the values of k for which primes 2kp + 1 can be found that divide the Mersenne numbers 2^{p}  1,
see the previous posts #29 and #30 at https://www.mersenneforum.org/showpo...4&postcount=29 and https://www.mersenneforum.org/showpo...2&postcount=30. For example, for p = 1277 (where p mod 4 = 1 and p mod 6 = 5), possible prime factors that divide M1277 have to be of the following forms (note that 3 + 4 = 7 and 3 × 4 = 12): 2(12m+3)p + 1, 2(12m+4)p + 1, 2(12m+7)p + 1, and 2(12(m+1))p + 1, m = 0, 1, 2,... It seems that the primes of the forms 2(12m+1)p + 1, 2(12m+5)p + 1, 2(12m+8)p + 1, 2(12m+9)p + 1, and 2(12m+11)p + 1, m = 0, 1, 2,..., cannot be factors of M1277. 
20220811, 13:16  #39 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2^{4}·3·211 Posts 
Can you also work this stuff (mod 4620) ?
Or, start with (mod 420) first... Last fiddled with by LaurV on 20220811 at 13:16 
20220811, 13:19  #40  
Feb 2017
Nowhere
13·461 Posts 
Quote:
It is also well known that if p is an odd prime, and q divides 2^p  1, then q = 2*k*p + 1 for some positive integer k. If p == 1 (mod 4) we then have 2*k*p + 1 == 2*k + 1 == 1 or 7 (mod 8). Thus, k == 0 or 3 (mod 4). For p == 1 (mod 4), this automatically rules out q = 2*k*p + 1 for k = 12*m + 1, 12*m + 5, or 12*m + 9 since 2*k*p + 1 == 3 (mod 8) for such k. 

20220811, 13:58  #41  
Jul 2022
2^{2}·13 Posts 
Quote:
I found this from an empirical observation but I think it is easy to prove that taking a prime number p we have (2^p  1)=7 (mod 8) or also (2^p  1)=1+2*p+8*p*k if p%4==3 , where % is the modulo operator or (2^p  1)=1+6*p+8*p*k if p%4==1 and if (2^p  1)=N1*N2 then N1=1 (mod 8) and N2=7 (mod 8) but also N1=1 (mod 2*p) and N2=1 (mod 2*p) then the only possible solution to find possible factors is this N1=1+8*p*k1 and N2=1+2*p+8*p*k2 if p%4==3 or N2=1+6*p+8*p*k2 if p%4==1 so if we exclude multiples of 3 for m>=0 N1=1+24*p*(m+1) or 1+16*p+24*p*m if p%6=1 N1=1+24*p*(m+1) or 1+ 8*p+24*p*m if p%6=5 and N2=1+10*p+24*p*m or 1+18*p+24*p*m if p%6=1 and p%4==3 N2=1+ 2*p+24*p*m or 1+18*p+24*p*m if p%6=5 and p%4==3 or N2=1+6*p+24*p*m or 1+22*p+24*p*m if p%6=1 and p%4==1 N2=1+6*p+24*p*m or 1+14*p+24*p*m if p%6=5 and p%4==1 Last fiddled with by User140242 on 20220811 at 14:52 

20220812, 07:43  #42  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2^{4}×3×211 Posts 
Quote:
As p is prime, it can only be 1 or 3 (mod 4), because it can not be even. 1. if p=1 (mod 4), then k can only be 0 or 3 (mod 4). 2. if p=3 (mod 4), then k can only be 0 or 1 (mod 4). Now stop here, the other stuff (mod 6, etc.) is not useful, as it doesn't reduce the searching space. Next step is to put 3 into equation, and find the classes of k, depending on the classes of p (mod 12). As p is prime, it can only be 1, 5, 7, or 11 (mod 12). What are the classes of k, in each case? 1. when p=1 (mod 12), k can only be ??? (mod 12) 2. when p=5 (mod 12), k can only be ??? (mod 12) 3. when p=7 (mod 12), k can only be ??? (mod 12) 4. when p=11 (mod 12), k can only be ??? (mod 12) Fill in the question marks. (You actually did this already, but in somehow obfuscated way, with (mod 4) and (mod 6)). Next step is to put 5 into equation, and find the classes of k, depending on the classes of p (mod 60). There are 16 classes of p (mod 60). Next step is to put 7 into equation, and find the classes of k, depending on the classes of p (mod 420). That is what (and why) I was asking you to do, in my previous post. There are 96 classes of p (mod 420). To find more about these numbers, and where do they come from, you can read about Euler's Phy function. Next step is to put 11 into equation, and find the classes of k, depending on the classes of p (mod 4620). There are 960 classes of p (mod 4620). If you succeed to reach this point, congratulations, you just discovered how mfaktc and its relatives work... Last fiddled with by LaurV on 20220812 at 08:03 

20220812, 08:08  #43  
Jul 2022
2^{2}×13 Posts 
Quote:
If a basis bW=8*p is used, the possible factors are of the type q = 1+8*k*p and q=1+2*p+8*k*p if p%4==3 or q=1+6*p+8*k*p if p%4==1. so there are 2 classes or possible remainders [1 , 1+2*p] if p%4==3 or [1 , 1+6*p] if p%4==1. If a basis bW=24*p is used as mentioned above, the possible factors are: Quote:


20220812, 08:15  #44  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2^{4}·3·211 Posts 
Quote:
Quote:
You still get 4 classes to test for factors; to reduce more the percentages, you need new primes in the modulo. Last fiddled with by LaurV on 20220812 at 09:07 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Repeating residues in LL tests of composite Mersenne numbers  Viliam Furik  Number Theory Discussion Group  22  20201208 14:45 
Mersenne number with exponent 333333367 is composite  TheGuardian  GPU Computing  25  20190509 21:53 
Factoring composite Mersenne numbers using Pollard Rho  jshort  Factoring  9  20190409 16:34 
2 holes in bizarre theorem about composite Mersenne Numbers  wildrabbitt  Math  120  20160929 21:52 
Factoring highly composite Mersenne numbers  philmoore  Factoring  21  20041118 20:00 