20020914, 00:09  #1 
Sep 2002
2^{2}×3×5 Posts 
Factors of Mersenne Numbers
I would like to know why a factor of a Mersenne number must be in the form of 2kp+1. I have read the proof, but I still don't understand. And does k have to be in a certain form?
Thanks. 
20020914, 05:11  #2  
Aug 2002
2·3·5 Posts 
I am assuming that you read the proof on Chris Caldwell's Prime Pages. I'll quote it:
Quote:
First off, in case you don't know, the statement "x = y (mod z)" is read "x is congruent to y modulo z". The equals sign should really have three horizontal lines in this notation, but we'll have to make do with two. The *meaning* of the statement is "When you divide x by z, the remainder is the same as the remainder when you divide y by z". Examples: 20 = 2 (mod 3)  20 / 3 = 6 with remainder 2 21 = 0 (mod 3)  21 / 3 = 7 with remainder 0 22 = 25 (mod 3)  22 / 3 = 7 with remainder 1; 25 / 3 = 8 with remainder 1 Modulo arithmetic makes number theory a lot easier. We'll need to know that if x = a (mod z) and y = b (mod z), then (x+y) = (a+b) (mod z). Also, x*y = a*b (mod z). Examples: 5 = 2 (mod 3) and 10 = 1 (mod 3) so 5 + 10 = 2 + 1 (mod 3), or 15 = 3 (mod 3. 5 * 10 = 2 * 1 (mod 3), or 50 = 2 (mod 3) We'll need to know this too: Definition: the order of a number x modulo another number y is the lowest power of x which is congruent to 1 modulo y. This number does not always exist, but when it does, it is at most equal to (y1). In our case, the orders we will be looking at are known to exist. Example: The order of 2 mod 5 is 4, since 2^4 = 16 = 1 (mod 5) The application of this is that if the order of x mod y is, say, 4, then x to any multiple of 4 is congruent to 1 modulo y. Also, *only* multiples of 4 have this property. Example: The order of 2 is 3 (mod 7) 2^3 = 8 = 1 (mod 7) 2^6 = 64 = 1 (mod 7) 2^1872459261927651 = (a huge number) = 1 (mod 7) Usage note: The term "divides" as used in this proof means "divides evenly". "p divides q" means p = 0 (mod q) On to the proof! Quote:
p divides Mq > Mq = 0 (mod p) > Mq + 1 = 1 (mod p) > (2^q  1) + 1 = 1 (mod p) > 2^q = 1 (mod p) Quote:
Quote:
Quote:
p1 = qr Now... p is odd, and so is q, so r must be even. So r = 2k for some number k. p1 = qr = 2kq > p = 2kq + 1 Which is the first half of our result. Quote:
Quote:
Example: 2 is a quadratic residue (mod 7) because 3^2 = 9 = 2 (mod 7). [Edit: ewmayer pointed out that my original explanation was incorrect. Here is his version:] 2^q = 1 (mod p) Multiplying by 2, we have 2^(q+1) = 2 (mod p), and since q odd, the exponent of 2 in the lefthand side is even, i.e. the LHS is a perfect square. Quote:
It is a useful fact because it allows you to eliminate any numbers which have remainder 3 or 5 when divided by 8. I should mention that p = 1 (mod 8) is another way of saying p = 7 (mod 8). I hope you made it to the bottom of the post without falling asleep, and I hope it helps![/b] 

20020914, 15:22  #3 
Aug 2002
37_{8} Posts 
Great explanations.
What propriety are you using to get this ? Mq + 1 = 1 (mod p) > (2^q  1) + 1 = 1 (mod p) 
20020914, 15:30  #4  
Aug 2002
2·3·5 Posts 
Quote:
Mq = 2^q  1. This is just a substitution step. 

20020914, 17:39  #5 
Sep 2002
2^{2}×3×5 Posts 
That was a good post, and I somewhat understand (I will need to read it again).
But you left one question unanswered (unless I missed it somewhere) but does k need to be in a certain form? Or can it be any random number (of course 2kp+1 might not divide the mersenne number if k is random)? I also note that you used an r, and you substituted it with a 2k because it is even. Therefore, what are the bounds of testing for k? Thanks. 
20020914, 18:05  #6  
Aug 2002
1E_{16} Posts 
Quote:
1 = 2*0*11 + 1 (k=0) 23 = 2*1*11 + 1 (k=1) 87 = 2*4*11 + 1 (k=4) 2047 = 2*93*11 + 1 (k=93) We *can* say that if Mp is not prime, then it has a factor other than 1 which is less than the square root of Mp. Thus only values of k for which 2kp + 1 < sqrt(Mp) need to be checked. This doesn't really limit k all that much unless p is really small. A rough bound can be found as follows: sqrt(Mp) = sqrt(2^p  1) < sqrt(2^p) = 2^(p/2) 2kp + 1 < 2^(p/2) 2kp < 2^(p/2) kp < 2^(p/2  1) k < 2^(p/2  1) / p If you try 11, you get k < 2^(4.5) / 11 = (approx) 2.057 < 3 So if you tried k=1 and k=2 and neither one resulted in a factor of M11, you would know M11 is prime. If p gets just a little bigger, the bound for k gets quite large. Substituting 127 gives you k < 2^(62.5) / 127 = (approx) 5.1 * 10^16 Which is an awful lot of k's. What is done in practice is that some small values of (2kp+1) are tried. This produces factors for quite a lot of Mp's. At a certain point, it doesn't pay off to try any more k's, because the bigger k is, the less chance (2kp + 1) is a factor. 

20020925, 13:16  #7 
23024_{8} Posts 
Actually k is slightly influenced by Zsigmondy's theorum
http://mathworld.wolfram.com/ZsigmondyTheorem.html 
20020925, 17:38  #8 
∂^{2}ω=0
Sep 2002
República de California
11628_{10} Posts 
toferc wrote (re. the special form 2qk + 1 of Mersenne factors)
>We know that 2 is a quadratic residue mod p because > >q is odd > qk is odd > qk + 1 is even > >2^(qk+1) is a perfect square > >2*(2^qk) is a perfect square Not quite. In fact, qk may be even or odd. Example the factors of M11 = 2^11  1 are 23 and 89; the first has k = 1 which gives qk = 11, the second has k = 4, which gives qk = 44. But in fact it's much easier to show that 2 is a quadratic residue modulo the factor p. First off, only factors of Mq with q odd have the special form in question, so we only consider oddprime q. Simply from the fact that p divides Mq, we have 2^q == 1 mod p. Multiplying by 2, we have 2^(q+1) == 2 mod p, and since q odd, the exponent of 2 in the lefthand side is even, i.e. the LHS is a perfect square. Another thing that bears mentioning is that in fact there are additional rigorous correlations between the Mersenne exponent q modulo 3,4,5,... and k mod 3,4,5,... . Exploiting the simplest few of these can reduce the number of k's we need to try to achieve a desired factorsize bound by 7580%. All the good factoring codes (including Prime95) do this, and also subject all candidates that survive the basic criteria (p = + 1 mod 8, p has k of the proper form modulo 3,4,5...) to a further small prime sieve to increase the odds that the candidate factor is prime. (Q Why don't we just subject p to a probableprime test? Answer Because doing that is about the same expense as testing whether 2^q == 1 mod p. In fact, if p has more bits than the Mersenne exponent q, which is generally the case for decently deep trial factoring work, it's MORE expensive to test p for probable primality than to test whether it divides Mq. Plus, if p did prove to be probableprime, we'd have to go ahead and see whether it divides Mq anyway.) Ernst 
20020925, 22:56  #9  
Sep 2002
2^{2}·3·5 Posts 
I have found this, but I am not sure about it (especially because it contains an error
Quote:


20020926, 02:00  #10  
Aug 2002
2×3×5 Posts 
Quote:
Thank you for clearing that up. Tofer 

20020926, 04:46  #11  
Aug 2002
2^{2}·13 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P1 factoring attempts at smallestremaining Mersenne numbers with no known factors  UberNumberGeek  Factoring  51  20170213 20:30 
Modular restrictions on factors of Mersenne numbers  siegert81  Math  23  20140318 11:50 
Mersenne prime factors of very large numbers  devarajkandadai  Miscellaneous Math  15  20120529 13:18 
Mersenne Prime Factors of v.large numbers  devarajkandadai  Miscellaneous Math  6  20060104 22:44 
Factors of Mersenne numbers ?  Fusion_power  Math  13  20031028 20:52 