20220420, 10:19  #23 
"Καλός"
May 2018
3×11^{2} Posts 
It should be noted that it is assumed that 6p + 1 is a prime number.
If 6p + 1 is not a prime number, there are instances when M_{p} mod (6p + 1) ≠ 0 and 6p + 1 = 27a^{2} + b^{2}, for example: p = 41, (2^{41}  1) mod (6×41 + 1) = 31 ≠ 0, and 6×41 + 1 = 27×3^{2} +2^{2}. 
20220420, 10:57  #24 
Mar 2021
France
41 Posts 
Yes of course 6*p+1 must be prime I guess but p isn't necessary prime.
For example : (6*21+1) = 127 divides (2^211) but 21 isn't prime. 
20220420, 12:58  #25  
"Καλός"
May 2018
3×11^{2} Posts 
Quote:
p = 21, 121, 153, 221, 237, 245, 305, 333, 357, 381, 445, 465, 545, 565, 605, 637, 657, 737, 753, 777, 793, 861, 917,... Code:
kc = 3; ic = 2; While[ic <= 1000, p = ic; Mn = 2^p  1; fc = 2*kc*p + 1; If[(Mod[p, 4] == 1) && (Mod[Mn, fc] == 0) && (PrimeQ[p] == False) && (PrimeQ[fc] == True), rc = FindInstance[{fc == 27*ac^2 + bc^2}, {ac, bc}, PositiveIntegers]; Print[p, " ", Mod[Mn, fc], " ", rc];]; Code:
21 0 {{ac>1,bc>10}} 121 0 {{ac>3,bc>22}} 153 0 {{ac>3,bc>26}} 221 0 {{ac>7,bc>2}} 237 0 {{ac>7,bc>10}} 245 0 {{ac>1,bc>38}} 305 0 {{ac>5,bc>34}} 333 0 {{ac>7,bc>26}} 357 0 {{ac>1,bc>46}} 381 0 {{ac>9,bc>10}} 445 0 {{ac>9,bc>22}} 465 0 {{ac>5,bc>46}} 545 0 {{ac>11,bc>2}} 565 0 {{ac>1,bc>58}} 605 0 {{ac>9,bc>38}} 637 0 {{ac>7,bc>50}} 657 0 {{ac>11,bc>26}} 737 0 {{ac>11,bc>34}} 753 0 {{ac>5,bc>62}} 777 0 {{ac>13,bc>10}} 793 0 {{ac>13,bc>14}} 861 0 {{ac>7,bc>62}} 917 0 {{ac>1,bc>74}} ... 

20220420, 13:47  #26 
Feb 2017
Nowhere
13544_{8} Posts 
The OP to this thread indicates that we're only interested in prime exponents p. (After all, Mersenne numbers with composite exponents have algebraic factorizations, so are already "known from number theory to be composite.")
It has long been known that if p = 4*n + 3 and q = 2*p + 1 = 8*n + 7 are both prime, then q divides 2^p  1. This is because the quadratic character of 2 (mod q) is determined by q (mod 8). For given k > 1, there is alas no similarly convenient criterion for when p and q = 2*k+p + 1 both being prime implies q divides 2^p  1. Since p = (q1)/2/k, we can say that 2^((q1)/2) == 1 (mod q), so that q == 1 or 7 (mod 8). This condition excludes k with k%4 = 2 from consideration. Suppose that k > 1, k%4 <> 2, p is prime, and q = 2*k*p + 1 is also prime. We can choose p%4 to insure that q%8 is 1 or 7:
I can confidently predict that q = 2*k*p + 1 will divide 2^p  1 for about 1/k of the primes p for which q is also prime, if p%4 is chosen so that 2 is a quadratic residue (mod q). I just can't predict which 1/k it will be. Here is an actual count for p < 10^8: Code:
? c1=0;c2=0;forprime(p=3,100000000,if(p%4==3,q=10*p+1;if(isprime(q),c1++;if(Mod(2,q)^p==1,c2++))));print(c1" "c2) 259346 51816 ? Last fiddled with by Dr Sardonicus on 20220420 at 19:17 Reason: clarification 
20220513, 05:43  #27 
"Καλός"
May 2018
363_{10} Posts 
Excluding the 3^{rd} Mersenne prime number M_{5} (for which p = 5, p mod 4 = 1, 2^{p}  1 = 6p + 1 = 27×1^{2} + 2^{2} = 31 is a prime, and also 2p + 1 = 11 is a prime):
1) Out of the total of 50,847,534 prime numbers 2 ≤ p ≤ 999,999,937, there are 1,046,030 prime exponents (2.057%) with composite Mersenne numbers M_{p} mod (6p + 1) = 0 for which p mod 4 = 1 and 6p + 1 = 27a^{2} + b^{2} is a prime. 2) Out of the said 1,046,030 prime exponents of composite Mersenne numbers, there are 55,953 prime exponents for which 2p + 1 is also a prime. Note: The conjecture in post #17 (https://www.mersenneforum.org/showpo...4&postcount=17) holds in the interval of prime exponents 2 ≤ p ≤ 999,999,937. Also, out of the total of 50,847,534 prime numbers 2 ≤ p ≤ 999,999,937, there are 3,138,462 prime numbers (p = 5 included) for which 6p + 1 is a prime. Here 3,138,462 = 3 × 1,046,031 (p = 5 included) + 369. Out of the said 3,138,462 prime numbers, there are 168,529 prime numbers (p = 5 included) for which 2p + 1 is also a prime. Here 168,529 = 3 × 55,954 (p = 5 included) + 667. 
20220522, 21:18  #28 
"Καλός"
May 2018
3×11^{2} Posts 
For k = 5, out of the total of 50,847,534 prime numbers 2 ≤ p ≤ 999,999,937, there are 408,660 prime exponents (0.8%) with composite Mersenne numbers M_{p} mod (10p + 1) = 0 for which p mod 4 = 3 and p mod 6 = 1.
Also, out of the total of 50,847,534 prime numbers 2 ≤ p ≤ 999,999,937, there are 4,084,314 prime numbers for which 10p + 1 is a prime. Here 4,084,314 = 2,043,235 (for which p mod 4 = 1) + 2,041,079 (for which p mod 4 = 3), 4,084,314 = 4,084,313 (for which p mod 6 = 1) + 1 (for which p = 3, 2^{3}  1 < 10×3 + 1), and 2,041,079 = 5 × 408,660  2,221. 
20220530, 22:54  #29 
"Καλός"
May 2018
3×11^{2} Posts 
Number of 2kp+1 primes for p within tne range 2 ≤ p ≤ 999,999,937 which divide the composite Mersenne numbers M_{p} = 2^{p}1 so that M_{p} mod (2kp+1) = 0:
k=1: 1655600 (for which p mod 4 = 3 and p mod 6 = 5); k=2: None; k=3: 1046030 (for which p mod 4 = 1 and 2×3p+1 = 27a^{2}+b^{2} is a prime); k=4: 773708 (for which p mod 6 = 5), however, 54990 primes are already counted for k=1 and k=3 as follows: for 41786 primes M_{p} mod (2p+1) = 0, and for 13204 primes M_{p} mod (6p+1) = 0; k=5: 408660 (for which p mod 4 = 3 and p mod 6 = 1); k=6: None; k=7: 258602 (for which p mod 4 = 1 and p mod 6 = 5), however, 15901 primes are already counted for k=3 and k=4 as follows: for 9327 primes M_{p} mod (6p+1) = 0, for 6751 primes M_{p} mod (8p+1) = 0, and for 9327+675115901=177 primes M_{p} mod (6p+1) = 0 and M_{p} mod (8p+1) = 0; ... 
20220609, 10:15  #30 
"Καλός"
May 2018
553_{8} Posts 
This is a continuation of the previous post #29 at https://www.mersenneforum.org/showpo...4&postcount=29.
… Number of 2kp+1 primes for p within the range 2 ≤ p ≤ 999,999,937 which divide the composite Mersenne numbers M_{p} = 2^{p}1 so that M_{p} mod (2kp+1) = 0: k=8: 375441 (for which p mod 6 = 1), however, 15228 primes are already counted for k=3 and k=5 as follows (note that k=8=3+5): for 9615 primes M_{p} mod (6p+1) = 0, and for 5613 primes M_{p} mod (10p+1) = 0; k=9: 331102 (for which p mod 4 = 3), however, 30369 primes are already counted for k=1,4,5 and 8 as follows (note that k=9=1+8=4+5): for 17824 primes M_{p} mod (2p+1) = 0, for 6240 primes M_{p} mod (8p+1) = 0, for 4931 primes M_{p} mod (10p+1) = 0, and for 2002 primes M_{p} mod (16p+1) = 0, so that 17824+6240+4931+200230369=628 Mersenne numbers have more than two factors; k=10: None; k=11: 149424 (for which p mod 4 = 1 and p mod 6 = 1), however, 6898 primes are already counted for k=3 and k=8 as follows (note that k=11=3+8): for 5127 primes M_{p} mod (6p+1) = 0, and for 1854 primes M_{p} mod (16p+1) = 0, so that 5127+18546898=83 Mersenne numbers have more than two factors; ... Last fiddled with by Dobri on 20220609 at 10:16 
20220806, 15:49  #31 
Mar 2021
France
29_{16} Posts 
Hi,
I noticed something about the prime of the form p and 8p+1 and their divisibility by 2^p1 If p = ((2a1)^2+64(2b1)^21)/8 and 8p+1 = (2a1)^2+64(2b1)^2, then 8p+1 divides 2^p1 To find the exponent I use this code on PARI GP : for(a=1, 1000, for(b=1, 1000, if(isprime((((2*a1)^2+64*(2*b1)^21)/8))&&isprime((2*a1)^2+64*(2*b1)^2), print(((2*a1)^2+64*(2*b1)^21)/8)))) But I don't how to sort by increasing order on PARI GP I don't know if it's useful and I didn't found a counterexample but this interesting I guess 
20220808, 05:30  #32  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2786_{16} Posts 
Quote:
And yes, this is an interesting find, I was not aware of. Up to now, we don't have a result that says anything about small factors of mersenne for exponents p which are prime and 1 (mod 4). For p=3 (mod 4) we have the SG result (if q=2p+1 is prime and p is 3 mod 4, than q divides m=2^p1). But there is no similar result known to me which is touching prime p which are 1 (mod 4). If the "trick" behind of those formulas (which I didn't check yet) can be proved, this is an interesting result, with some mild theoretic value. And no, this is not "useful" in practice, there is no practical value, the factors it uncovers are very small, only 8 times the value of p, which are eliminated by initial sieving/TF in the first millisecond (for k=4, in q=2kp+1). Related to "sorting" in pari, you can add all the things to a list and use the sorting functions, if you need, or put everything in a file and sort it externally, but this effort is not really justified if you observe that the part coming from your "b" is much higher than the part from "a", so if you move b to external loop, they come out pretty sorted... Code:
for(b=1, 100, for(a=1, 100, q=(2*a1)^2+64*(2*b1)^2; p=(q1)/8; if(isprime(p)&&isprime(q), print(q", divides 2^"p"1")))) Edit: Ok. Using these 3 lines, one by one, in order, we get: Code:
gp> cnt=0; for(b=1, 1000, for(a=1, 1000, q=(2*a1)^2+64*(2*b1)^2; p=(q1)/8; if(isprime(p)&&isprime(q), cnt++; print(cnt": "q", "p)))) (6421 results are printed) gp> cnt=0; for(b=1, 1000, for(a=1, 1000, q=(2*a1)^2+64*(2*b1)^2; p=(q1)/8; if(isprime(p)&&isprime(q)&&Mod(2,q)^p==1, cnt++; print(cnt": "q", "p)))) (6421 results are printed) gp> cnt=0; for(b=1, 1000, for(a=1, 1000, q=(2*a1)^2+64*(2*b1)^2; p=(q1)/8; if(isprime(p)&&isprime(q)&&Mod(2,q)^p==1&&Mod(p,4)==1, cnt++; print(cnt": "q", "p)))) (3420 results are printed) Buddy, you are onto something... Last fiddled with by LaurV on 20220808 at 06:00 

20220808, 11:42  #33  
Apr 2020
857_{10} Posts 
Quote:
You've rediscovered an old result on when 2 is an 8th power modulo a prime. Reuschle (1856) stated, and Western (1911) proved, that if q is a prime of the form 8k+1:  If k is even, then 2 is an 8th power mod q if and only if q is of the form x^2 + 256y^2  If k is odd, then 2 is an 8th power mod q if and only if q is of the form x^2 + 64y^2 but not of the form x^2 + 256y^2. Here we are in the k odd case, and your (2a1)^2+64(2b1)^2 exactly corresponds to saying that 8p+1 is of the form x^2 + 64y^2 but not of the form x^2 + 256y^2. So in fact we can strengthen your statement to an "if and only if". 

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 