mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Dobri

Reply
 
Thread Tools
Old 2022-04-20, 10:19   #23
Dobri
 
"Καλός"
May 2018

17×19 Posts
Default

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 Mp mod (6p + 1) ≠ 0 and 6p + 1 = 27a2 + b2, for example:
p = 41, (241 - 1) mod (6×41 + 1) = 31 ≠ 0, and 6×41 + 1 = 27×32 +22.
Dobri is offline   Reply With Quote
Old 2022-04-20, 10:57   #24
kijinSeija
 
Mar 2021
France

2×3×5 Posts
Default

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^21-1) but 21 isn't prime.
kijinSeija is offline   Reply With Quote
Old 2022-04-20, 12:58   #25
Dobri
 
"Καλός"
May 2018

17×19 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
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^21-1) but 21 isn't prime.
This forms a sequence of composite p values indeed,
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}}
...
Dobri is offline   Reply With Quote
Old 2022-04-20, 13:47   #26
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

133128 Posts
Default

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 = (q-1)/2/k, we can say that 2^((q-1)/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:
  • If k%4 = 0, p == 1 or 3 (mod 4)
  • If k == 1 (mod 4) then p == 3 (mod 4)
  • If k == 3 (mod 4) then p == 1 (mod 4).
AFAIK the fastest way to determine whether q = 2*k*p + 1 divides 2^p - 1 for k > 1 is to test whether Mod(2,q)^p == 1.

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
?
The proportion of primes p == 3 (mod 4) such that q = 10*p + 1 is also prime, for which q also divides 2^p - 1, is 0.19979+ which is pretty close to 1/5.

Last fiddled with by Dr Sardonicus on 2022-04-20 at 19:17 Reason: clarification
Dr Sardonicus is offline   Reply With Quote
Old 2022-05-13, 05:43   #27
Dobri
 
"Καλός"
May 2018

32310 Posts
Default

Excluding the 3rd Mersenne prime number M5 (for which p = 5, p mod 4 = 1, 2p - 1 = 6p + 1 = 27×12 + 22 = 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 Mp mod (6p + 1) = 0 for which p mod 4 = 1 and 6p + 1 = 27a2 + b2 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.
Dobri is offline   Reply With Quote
Old 2022-05-22, 21:18   #28
Dobri
 
"Καλός"
May 2018

14316 Posts
Default

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 Mp 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, 23 - 1 < 10×3 + 1), and
2,041,079 = 5 × 408,660 - 2,221.
Dobri is offline   Reply With Quote
Old 2022-05-30, 22:54   #29
Dobri
 
"Καλός"
May 2018

32310 Posts
Default

Number of 2kp+1 primes for p within tne range 2 ≤ p ≤ 999,999,937 which divide the composite Mersenne numbers Mp = 2p-1 so that Mp 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 = 27a2+b2 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 Mp mod (2p+1) = 0, and for 13204 primes Mp 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 Mp mod (6p+1) = 0, for 6751 primes Mp mod (8p+1) = 0, and for 9327+6751-15901=177 primes Mp mod (6p+1) = 0 and Mp mod (8p+1) = 0;
...
Dobri is offline   Reply With Quote
Old 2022-06-09, 10:15   #30
Dobri
 
"Καλός"
May 2018

32310 Posts
Default

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 Mp = 2p-1 so that Mp 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 Mp mod (6p+1) = 0, and for 5613 primes Mp 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 Mp mod (2p+1) = 0, for 6240 primes Mp mod (8p+1) = 0, for 4931 primes Mp mod (10p+1) = 0, and for 2002 primes Mp mod (16p+1) = 0, so that 17824+6240+4931+2002-30369=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 Mp mod (6p+1) = 0, and for 1854 primes Mp mod (16p+1) = 0, so that 5127+1854-6898=83 Mersenne numbers have more than two factors;
...

Last fiddled with by Dobri on 2022-06-09 at 10:16
Dobri is offline   Reply With Quote
Reply

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 2020-12-08 14:45
Mersenne number with exponent 333333367 is composite TheGuardian GPU Computing 25 2019-05-09 21:53
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
2 holes in bizarre theorem about composite Mersenne Numbers wildrabbitt Math 120 2016-09-29 21:52
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 06:47.


Mon Jul 4 06:47:52 UTC 2022 up 81 days, 4:49, 0 users, load averages: 2.58, 1.60, 1.30

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔