mersenneforum.org  

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

Reply
 
Thread Tools
Old 2022-04-17, 16:08   #1
Dobri
 
"Καλός"
May 2018

5·73 Posts
Default Mersenne Numbers Known from Number Practice to Be Composite

The Mersenne numbers with prime exponents p > 3 for which p mod 4 = 3 and 2p + 1 is a prime number are known to be composite.
Out of the total of 50,847,534 prime exponents 2 ≤ p ≤ 999,999,937, there are 1,655,600 prime exponents (3.256%) satisfying the aforesaid conditions.
Perhaps GIMPS could add notifications that the corresponding Mersenne numbers are known to be composite from elementary number theory.
The compressed list of the 1,655,600 prime exponents from 11 to 999,999,191 exceeds the limit of 4 MB.
Therefore, a Wolfram code that saves the prime exponents in a file is given below instead.
Code:
SetDirectory[NotebookDirectory[]]; fname = NotebookDirectory[] <> "Mp3mod4and2pplus1.dat"; file = File[fname]; If[FileExistsQ[file] == False, OpenWrite[file]; Close[file];]; 
OpenAppend[file];
Np = PrimePi[999999937]; Pcount = 0;
ic = 3; While[ic <= Np, p = Prime[ic]; If[(Mod[p, 4] == 3) && (PrimeQ[2*p + 1] == True), Pcount++; Write[file, p];]; ic++;];
Close[file]; Print[Pcount];
Dobri is offline   Reply With Quote
Old 2022-04-17, 21:42   #2
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

153378 Posts
Default

How many don't already have known factors?
kriesel is offline   Reply With Quote
Old 2022-04-17, 22:19   #3
mathwiz
 
Mar 2019

3·101 Posts
Default

Quote:
Originally Posted by Dobri View Post
The Mersenne numbers with prime exponents p > 3 for which p mod 4 = 3 and 2p + 1 is a prime number are known to be composite.
More precisely, \(2p + 1\) divides \(M_p\) for the case you described. So all of these Mersenne numbers have known (small) factors, and all of them should be in the database already.
mathwiz is offline   Reply With Quote
Old 2022-04-17, 22:23   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,389 Posts
Default

Yes they have the smallest factor 2kp+1 with k=1, so they were found back in ~1996 (or 2008 when the range extended to 1 billion). No "elementary" tricks will improve on a project running for 25-26 years.

GIMPS did have major improvements in the last 3-7 years with Jacobi check, Gerbicz error checking and finally PRP proofs, but they were far from elementary.

Last fiddled with by ATH on 2022-04-17 at 22:27
ATH is offline   Reply With Quote
Old 2022-04-18, 14:06   #5
Dobri
 
"Καλός"
May 2018

5·73 Posts
Default

The information in this thread is provided for completeness and is not concerned with novelty indeed.
Searching for "1655600", two previous posts on the topic can be located, see
https://www.mersenneforum.org/showth...600#post300787 and
https://www.mersenneforum.org/showth...600#post180704.
Dobri is offline   Reply With Quote
Old 2022-04-18, 15:42   #6
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72×73 Posts
Default

For p == 3 mod 4, 2*p+1 (if it is prime) always divides 2^p-1 (this is even true if p itself is not prime)

There should be conditions that 4*p+1, 6*p+1, 8*p+1, etc. always divides 2^p-1

You can check the sequence https://oeis.org/A001917, for q == 1, 7 mod 8, A001917(primepi(q)) is even, and for q == 1, 7 mod 8, A001917(primepi(q)) is odd, thus for p == 3 mod 4, A001917(primepi(2*p+1)) is even, and hence 2*p+1 must divide 2^p-1, you can also check that for which prime q, A001917(primepi(q)) is divisible by 3, 4, 5, 6, etc.
sweety439 is offline   Reply With Quote
Old 2022-04-18, 16:15   #7
kijinSeija
 
Mar 2021
France

4110 Posts
Default

Quote:
Originally Posted by sweety439 View Post
For p == 3 mod 4, 2*p+1 (if it is prime) always divides 2^p-1 (this is even true if p itself is not prime)

There should be conditions that 4*p+1, 6*p+1, 8*p+1, etc. always divides 2^p-1

You can check the sequence https://oeis.org/A001917, for q == 1, 7 mod 8, A001917(primepi(q)) is even, and for q == 1, 7 mod 8, A001917(primepi(q)) is odd, thus for p == 3 mod 4, A001917(primepi(2*p+1)) is even, and hence 2*p+1 must divide 2^p-1, you can also check that for which prime q, A001917(primepi(q)) is divisible by 3, 4, 5, 6, etc.
4p+1 never divides 2^p-1 right ? I can't find the sequences in OEIS
kijinSeija is offline   Reply With Quote
Old 2022-04-18, 16:37   #8
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72·73 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
4p+1 never divides 2^p-1 right ? I can't find the sequences in OEIS
Right, since 4p+1 is always == 5 mod 8, and for q == 5 mod 8, A001917(primepi(q)) is always odd and cannot be 4
sweety439 is offline   Reply With Quote
Old 2022-04-18, 16:41   #9
kijinSeija
 
Mar 2021
France

4110 Posts
Default

Quote:
Originally Posted by sweety439 View Post
Right, since 4p+1 is always == 5 mod 8, and for q == 5 mod 8, A001917(primepi(q)) is always odd and cannot be 4
Thanks for your answer.

By the way, do you know the condition for example 6*p+1 or 10*p+1 divides 2^p-1 ?

I know the condition for 2*p+1 but I have no idea for these two for example.
kijinSeija is offline   Reply With Quote
Old 2022-04-18, 17:15   #10
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72·73 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
Thanks for your answer.

By the way, do you know the condition for example 6*p+1 or 10*p+1 divides 2^p-1 ?

I know the condition for 2*p+1 but I have no idea for these two for example.
No, I want to know how to compute A001917(q) for an odd prime q with given congruent class mod some numbers (say 8 or 24), I want to know the condition for A001917(q) is divisible by given number r, it is equivalent to 2 is r-th power residue (quadratic residue for r=2, cubic residue for r=3, quartic residue for r=4, etc., we should use cubic reciprocity and quartic reciprocity to solve, I do not think it can be solved for r>4 (except r=8 and r=16), since a general quintic equation cannot be solved algebraically) mod q (where r is the largest such number dividing q-1), such prime q must divide Phi((q-1)/r,2), where Phi is the cyclotomic polynomial, and (let p = (q-1)/r) if p is prime, then this is 2^p-1, if p is twice a prime, then this is the Wagstaff number (2^(p/2)+1)/3, and if p is power of 2, then this is the Fermat number 2^(p/2)+1
sweety439 is offline   Reply With Quote
Old 2022-04-18, 19:25   #11
charybdis
 
charybdis's Avatar
 
Apr 2020

35916 Posts
Default

Quote:
Originally Posted by sweety439 View Post
I do not think it can be solved for r>4 (except r=8 and r=16), since a general quintic equation cannot be solved algebraically
Well you didn't think enough. This has absolutely nothing to do with the unsolvability of the general quintic.

First, you use the phrase "cannot be solved" but you don't understand what it means in this context. Over the reals or the complex numbers, it means that we *literally cannot write down the solutions*. But here we're working over a finite field, namely the integers modulo some prime. So even though it isn't easy to find solutions to x^5 = 2, it is certainly possible to write them down if they exist. And secondly, while a general quintic cannot be solved over the complex numbers, the quintic x^5 = 2 most definitely can!

Conditions for 2 to be a quintic residue mod p do exist although they are not convenient to use. This can be done for higher order roots too but the conditions will get even worse.
charybdis 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 19:52.


Thu Oct 6 19:52:53 UTC 2022 up 49 days, 17:21, 0 users, load averages: 1.31, 1.23, 1.22

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.

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