mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2011-11-26, 09:55   #1
princeps
 
Nov 2011

22×3 Posts
Default 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 ?
princeps is offline   Reply With Quote
Old 2011-11-26, 16:15   #2
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5×359 Posts
Default

Our resident curmudgeon is out.
Can you define the \wedge (wedge) operator so more of the amateurs can follow a little better?
Christenson is offline   Reply With Quote
Old 2011-11-26, 16:47   #3
princeps
 
Nov 2011

C16 Posts
Default

definition of logical conjunction which math symbol is : \wedge
princeps is offline   Reply With Quote
Old 2011-11-26, 19:36   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by princeps View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-11-26, 20:33   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2011-11-26, 21:56   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

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.
science_man_88 is offline   Reply With Quote
Old 2011-11-27, 05:33   #7
princeps
 
Nov 2011

22×3 Posts
Default

Quote:
Originally Posted by akruppa View Post
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 ?
princeps is offline   Reply With Quote
Old 2011-11-27, 16:16   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by princeps View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-11-28, 08:09   #9
princeps
 
Nov 2011

22·3 Posts
Default

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...
princeps is offline   Reply With Quote
Old 2011-11-28, 09:08   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×349 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2011-11-28, 13:47   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


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

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


Fri Oct 15 23:44:59 UTC 2021 up 84 days, 18:13, 0 users, load averages: 0.92, 1.07, 1.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.