mersenneforum.org Some Properties of Mersenne Number Factors
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-11-26, 09:55 #1 princeps   Nov 2011 1210 Posts Some Properties of Mersenne Number Factors $M_p=2^p-1$ a) $(q=k\cdot 2^3+1 \wedge M_p \equiv 0 \pmod q) \Rightarrow (k\equiv 0 \pmod p \wedge \gcd(k-1,3)=1)$ b) $(q=k\cdot 2^3-1 \wedge M_p \equiv 0 \pmod q) \Rightarrow (4 \cdot k\equiv 1 \pmod p \wedge \gcd(k+1,3)=1)$ Am I correct ?
 2011-11-26, 16:15 #2 Christenson     Dec 2010 Monticello 111000000112 Posts Our resident curmudgeon is out. Can you define the$\wedge$(wedge) operator so more of the amateurs can follow a little better?
 2011-11-26, 16:47 #3 princeps   Nov 2011 C16 Posts definition of logical conjunction which math symbol is : $\wedge$
2011-11-26, 19:36   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by princeps $M_p=2^p-1$ a) $(q=k\cdot 2^3+1 \wedge M_p \equiv 0 \pmod q) \Rightarrow (k\equiv 0 \pmod p \wedge \gcd(k-1,3)=1)$ b) $(q=k\cdot 2^3-1 \wedge M_p \equiv 0 \pmod q) \Rightarrow (4 \cdot k\equiv 1 \pmod p \wedge \gcd(k+1,3)=1)$ Am I correct ?
I'm not sure can't say the gcd stuff for sure but since$q=2\cdot j\cdot p+1= k\cdot 2^3+1$;$j\cdot p = k\cdot 2^2$ so the $k\equiv 0 \text { (mod p)}$ is true. for the gcd to be correct you have to prove $k\neq 1 \text { (mod 3)}$ if $q=k\cdot 2^3-1=2\cdot j\cdot p+1$ then $k\cdot 2^2 \equiv 2 \text{ (mod } j\cdot p \text{)}$. you may complete the thought process if you want I've been sitting or walking down at the market for 6+ hour after 8 hours of poor if any sleep.

 2011-11-26, 20:33 #5 akruppa     "Nancy" Aug 2002 Alexandria 246710 Posts a) Prime factors q of Mp with p an odd prime are always 1 (mod p) and +-1 (mod 8), so k==0 (mod p) in your notation is correct. If 3|(k-1), then 8k == 2 (mod 3) and q = 8k+1 == 0 (mod 3), which would make q not a prime factor. So gcd(k-1, 3)=1. b) q = 8k-1 = lp+1, so 8k = lp+2, so 8k == 2 (mod p) <=> 4k == 1 (mod p). If k+1 were divisible by 3, etc., as above, just with signs changed. Last fiddled with by akruppa on 2011-11-26 at 20:33
 2011-11-26, 21:56 #6 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts Code: b=[];forstep(p=6*80+5,1,[-4,-2],if(isprime(p),forstep(y=1,100000*p+1,if(p%6==1,[4*p,2*p],[2*p,4*p]),if(isprime(y)&&(2^p-1)%y==0,if(isprime((y-1)/(2*p)),b=concat(b,[[(y-1)/(2*p),p]]);break()))))) is this any good timing it as is I got about 12-13 seconds , without the prime check for y I get about 4-5 seconds.
2011-11-27, 05:33   #7
princeps

Nov 2011

11002 Posts

Quote:
 Originally Posted by akruppa a) Prime factors q of Mp with p an odd prime are always 1 (mod p) and +-1 (mod 8), so k==0 (mod p) in your notation is correct. If 3|(k-1), then 8k == 2 (mod 3) and q = 8k+1 == 0 (mod 3), which would make q not a prime factor. So gcd(k-1, 3)=1. b) q = 8k-1 = lp+1, so 8k = lp+2, so 8k == 2 (mod p) <=> 4k == 1 (mod p). If k+1 were divisible by 3, etc., as above, just with signs changed.
What do you think...Are there more similar conditions for$k$ ?

2011-11-27, 16:16   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by princeps What do you think...Are there more similar conditions for$k$ ?
could be I tried using mod 24 before but I can't remember where on here or otherwise I put the result. I started from the fact that $Mp\equiv 7 \text {(mod 24)}$

Last fiddled with by science_man_88 on 2011-11-27 at 16:18

 2011-11-28, 08:09 #9 princeps   Nov 2011 C16 Posts The another property of prime factor $q$ is : $(M_p\equiv0\pmod q \wedge q\equiv 1 \pmod 8) \Rightarrow q\equiv 1 \pmod {8\cdot p}$ This can be proved by Fermat's Little Theorem...
 2011-11-28, 09:08 #10 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 233538 Posts You don't need FT to prove that. Simple algebraic calculus shows it. All factors of mersenne numbers M=2^p-1 with p prime (in fact odd p is enough) can only be of the form 2*k*p+1 for some k, and they can only be of the form 8*x+1 or 8*x-1 for some x. So, you split in two cases: (1). The factor is 8*x+1 and 2*k*p+1, equate them, take the 1 out, simplify by 2, so kp=4x, and p is prime and 4 is a prime power, it follows that x contains p and k contains 4, so k is a multiple of 4, and all factors of this form are in fact (by re-notating k): 8*k*p+1, for any k bigger or equal to 1. (2). The factor is 8*x-1 and 2*k*p+1, equate them, move the 1 on the other side, simplify by 2, etc etc, you will reach some conclusion like the factors can only be (re-notating k): 8*k*p+s*p+1, where k bigger or equal to 0, and s is the double of the complement of p (mod 4). That is: if p=1 (mod 4) then s=6 and if p=3 (mod 4) then s=2. So this case splits in: (2a). Factor is 8*k*p+2*p+1 if p=3 (mod 4) and (2b). Factor is 8*k*p+6*p+1 if p=1 (mod 4), where k>=0 in both situations. You can call the factors of the form (1) "plus factors", and the factors of the form (2a) or (2b) "minus factors". This is all you can make from the discussion in this thread, and from all discussions related to the form of the factors. There are no other relations you can deduct from it for the form of the factors, even if you take them mod 4, mod 3, mod 24, mod whatever, unless you discover something really NEW about the form of the factors. All attempts lead more or less to this, after more or less circling around the tail. This is the strongest (known) conclusion that you can get, and includes all the stuff with the powers of 3 or other things written before in this thread. There were plenty of discussion on the forum about it. This is just wasting time. edit: Please remark that it is not necessary that a mersenne M to have "plus factors" (it can have none), but if M is composite, it will always have an odd number of "minus factors", that is: it will have at least one minus factor (or 3, or 5, etc). The "minus factors" can not be in even number, otherwise multiplying them will lead to a number which is 1 (mod 8) and M is 7 (mod 8) - impossible. That is because multiplying by "plus" factors does not change the class (the number stays 1 mod 8 if it was 1 mod 8, and it stays 7 mod 8 if it was 7 mod 8). So only multiplying with "minus" factors can change the class. This means "it could make sense" to search for "that minus factor", and some searching was indeed conducted to look for it, as you can sieve them 4 times higher, but the disadvantage is that nobody tells you that the "minus" factor is the lowest (generally, they are not, ex: for M29, "plus" factors are 233 and 2089, and the "minus" factor is 1103). Last fiddled with by LaurV on 2011-11-28 at 09:55
2011-11-28, 13:47   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by LaurV You don't need FT to prove that. Simple algebraic calculus shows it. All factors of mersenne numbers M=2^p-1 with p prime (in fact odd p is enough) can only be of the form 2*k*p+1 for some k, and they can only be of the form 8*x+1 or 8*x-1 for some x. So, you split in two cases: (1). The factor is 8*x+1 and 2*k*p+1, equate them, take the 1 out, simplify by 2, so kp=4x, and p is prime and 4 is a prime power, it follows that x contains p and k contains 4, so k is a multiple of 4, and all factors of this form are in fact (by re-notating k): 8*k*p+1, for any k bigger or equal to 1. (2). The factor is 8*x-1 and 2*k*p+1, equate them, move the 1 on the other side, simplify by 2, etc etc, you will reach some conclusion like the factors can only be (re-notating k): 8*k*p+s*p+1, where k bigger or equal to 0, and s is the double of the complement of p (mod 4). That is: if p=1 (mod 4) then s=6 and if p=3 (mod 4) then s=2. So this case splits in: (2a). Factor is 8*k*p+2*p+1 if p=3 (mod 4) and (2b). Factor is 8*k*p+6*p+1 if p=1 (mod 4), where k>=0 in both situations. You can call the factors of the form (1) "plus factors", and the factors of the form (2a) or (2b) "minus factors". This is all you can make from the discussion in this thread, and from all discussions related to the form of the factors. There are no other relations you can deduct from it for the form of the factors, even if you take them mod 4, mod 3, mod 24, mod whatever, unless you discover something really NEW about the form of the factors. All attempts lead more or less to this, after more or less circling around the tail. This is the strongest (known) conclusion that you can get, and includes all the stuff with the powers of 3 or other things written before in this thread. There were plenty of discussion on the forum about it. This is just wasting time. edit: Please remark that it is not necessary that a mersenne M to have "plus factors" (it can have none), but if M is composite, it will always have an odd number of "minus factors", that is: it will have at least one minus factor (or 3, or 5, etc). The "minus factors" can not be in even number, otherwise multiplying them will lead to a number which is 1 (mod 8) and M is 7 (mod 8) - impossible. That is because multiplying by "plus" factors does not change the class (the number stays 1 mod 8 if it was 1 mod 8, and it stays 7 mod 8 if it was 7 mod 8). So only multiplying with "minus" factors can change the class. This means "it could make sense" to search for "that minus factor", and some searching was indeed conducted to look for it, as you can sieve them 4 times higher, but the disadvantage is that nobody tells you that the "minus" factor is the lowest (generally, they are not, ex: for M29, "plus" factors are 233 and 2089, and the "minus" factor is 1103).
really what happens with this:

Code:
(09:43)>forprime(x=5,100,print((2^x-2)/(2*x)))
3
9
93
315
3855
13797
182361
9256395
34636833
1857283155
26817356775
102280151421
1497207322929
84973577874915
4885260612740877
18900352534538475
1101298153654301589
16628050996019877513
64689951820132126215
3825714619033636628817
58261485282632731311141
3477359660913989536233495
816785180559426160758185055
(09:43)>((2*k*p+1)*(2*j*p+1))/(2*x)
%1 = (4*j*k*p^2 + (2*k + 2*j)*p + 1)/(2*x)
(09:44)>((2*k*p+1)*(2*j*p+1))/(2*p)
%2 = (4*j*k*p^2 + (2*k + 2*j)*p + 1)/(2*p)
(09:44)>(2*k*p+1)*(2*j*p+1)
%3 = 4*j*k*p^2 + (2*k + 2*j)*p + 1
(09:45)>((2*k*p+1)*(2*j*p+1)-1)/(2*p)
%4 = 2*j*k*p + (k + j)
yes I messed up a few times, if 2^p-1 = 2*l*p+1 for p>5, l=0 mod 3 and 2*j*k*p + (k + j) is as well assigning properties to p what do we get of j and k ? I forgot I tested it before and realize it leads to nothing that I could come up with that was useful.

Last fiddled with by science_man_88 on 2011-11-28 at 13:51

 Similar Threads Thread Thread Starter Forum Replies Last Post michael Math 31 2015-09-04 05:57 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 henryzz Math 7 2012-05-23 01:13 kurtulmehtap Math 31 2011-01-10 00:15 kurtulmehtap Math 12 2010-05-03 14:02

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

Wed May 25 10:23:29 UTC 2022 up 41 days, 8:24, 0 users, load averages: 1.64, 1.37, 1.21

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.

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