mersenneforum.org Some Properties of Mersenne Number Factors
 Register FAQ Search Today's Posts Mark Forums Read

 2011-11-26, 09:55 #1 princeps   Nov 2011 C16 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 5·359 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 11002 Posts definition of logical conjunction which math symbol is : $\wedge$
2011-11-26, 19:36   #4
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 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 2,467 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 Dartmouth NS 203428 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

1210 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
Dartmouth NS

2·3·23·61 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 22×3 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 19×541 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
Dartmouth NS

100000111000102 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 05:05.

Fri Feb 3 05:05:34 UTC 2023 up 169 days, 2:34, 1 user, load averages: 2.44, 1.52, 1.08