mersenneforum.org Mersenne Numbers Known from Number Theory to Be Composite
 Register FAQ Search Today's Posts Mark Forums Read

 2022-04-17, 16:08 #1 Dobri   "Καλός" May 2018 17×19 Posts Mersenne Numbers Known from Number Theory 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];
 2022-04-17, 21:42 #2 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 26·103 Posts How many don't already have known factors?
2022-04-17, 22:19   #3
mathwiz

Mar 2019

11716 Posts

Quote:
 Originally Posted by Dobri 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.

 2022-04-17, 22:23 #4 ATH Einyen     Dec 2003 Denmark 23·3·139 Posts 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
 2022-04-18, 14:06 #5 Dobri   "Καλός" May 2018 32310 Posts 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.
 2022-04-18, 15:42 #6 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 3,461 Posts 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.
2022-04-18, 16:15   #7
kijinSeija

Mar 2021
France

2×3×5 Posts

Quote:
 Originally Posted by sweety439 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

2022-04-18, 16:37   #8
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

3,461 Posts

Quote:
 Originally Posted by kijinSeija 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

2022-04-18, 16:41   #9
kijinSeija

Mar 2021
France

368 Posts

Quote:
 Originally Posted by sweety439 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

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.

2022-04-18, 17:15   #10
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

3,461 Posts

Quote:
 Originally Posted by kijinSeija 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

2022-04-18, 19:25   #11
charybdis

Apr 2020

7·107 Posts

Quote:
 Originally Posted by sweety439 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Viliam Furik Number Theory Discussion Group 22 2020-12-08 14:45 TheGuardian GPU Computing 25 2019-05-09 21:53 jshort Factoring 9 2019-04-09 16:34 wildrabbitt Math 120 2016-09-29 21:52 philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 07:10.

Mon Jul 4 07:10:00 UTC 2022 up 81 days, 5:11, 0 users, load averages: 0.87, 1.05, 1.12

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.

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