Some Properties of Mersenne Number Factors

princeps · 2011-11-26, 09:55

$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 ?

Christenson · 2011-11-26, 16:15

Our resident curmudgeon is out.
Can you define the $\wedge$ (wedge) operator so more of the amateurs can follow a little better?

princeps · 2011-11-26, 16:47

definition of logical conjunction which math symbol is : $\wedge$

science_man_88 · 2011-11-26, 19:36

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.

akruppa · 2011-11-26, 20:33

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.

science_man_88 · 2011-11-26, 21:56

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.

princeps · 2011-11-27, 05:33

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$ ?

science_man_88 · 2011-11-27, 16:16

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)}$

princeps · 2011-11-28, 08:09

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...

LaurV · 2011-11-28, 09:08

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).

science_man_88 · 2011-11-28, 13:47

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.

2011-11-26, 09:55	#1
princeps Nov 2011 2²·3 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, 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 2·3·23·61 Posts	Code: b=[];forstep(p=680+5,1,[-4,-2],if(isprime(p),forstep(y=1,100000p+1,if(p%6==1,[4p,2p],[2p,4p]),if(isprime(y)&&(2^p-1)%y==0,if(isprime((y-1)/(2p)),b=concat(b,[[(y-1)/(2p),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-28, 09:08	#10
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 24051₈ 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 2kp+1 for some k, and they can only be of the form 8x+1 or 8x-1 for some x. So, you split in two cases: (1). The factor is 8x+1 and 2kp+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): 8kp+1, for any k bigger or equal to 1. (2). The factor is 8x-1 and 2kp+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): *8kp+sp+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 8kp+2p+1 if p=3 (mod 4) and (2b). Factor is 8kp+6p+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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Special Form of Mersenne and Fermat Number Factors	michael	Math	31	2015-09-04 05:57
Number of distinct prime factors of a Double Mersenne number	aketilander	Operazione Doppi Mersennes	1	2012-11-09 21:16
Estimating the number of prime factors a number has	henryzz	Math	7	2012-05-23 01:13
Properties of Mersenne numbers	kurtulmehtap	Math	31	2011-01-10 00:15
Number of Factors for a Mersenne Number	kurtulmehtap	Math	12	2010-05-03 14:02

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 1100₂ Posts	definition of logical conjunction which math symbol is : $\wedge$

2011-11-28, 08:09	#9
princeps Nov 2011 C₁₆ 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...