 mersenneforum.org > Math Factors of Mersenne Numbers
 Register FAQ Search Today's Posts Mark Forums Read  2002-09-14, 00:09 #1 asdf   Sep 2002 22·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.   2002-09-14, 05:11   #2
toferc

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:
 Let p and q be odd primes. If p divides Mq, then p = 1 (mod q) and p = +/-1 (mod 8). Below we give a proof and an example. Proof. If p divides Mq, then 2^q = 1 (mod p) and the order of 2 (mod p) divides the prime q, so it must be q. By Fermat's Little Theorem the order of 2 also divides p-1, so p-1 = 2kq. This gives 2^[(p-1)/2] = 2^qk = 1 (mod p) so 2 is a quadratic residue mod p and it follows p = +/-1 (mod 8), which completes the proof.
This proof is not very user-friendly unless you happen to know the number theory involved, I'll try to explain it a little better. Since I don't know who is going to read this, I'll try to be pretty basic, nobody should think I'm trying to insult their intelligence.

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 (y-1). 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:
 If p divides Mq, then 2^q = 1 (mod p)
We are about to look at things that are true for all numbers p which are factors of Mq.

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:
 and the order of 2 (mod p) divides the prime q, so it must be q.
We know that the order divides q because only numbers x which are even multiples of the order have the property 2^x = 1 (mod p). However, the only numbers which divide q are 1 and q. The order can't be 1, so it must be q.

Quote:
 By Fermat's Little Theorem the order of 2 also divides p-1
Let's just say that this is true. Trying to understand FLT is left to the reader ;)

Quote:
 so p-1 = 2kq
Remember that the order is q, so p-1 is some multiple of q, call it r.

p-1 = qr

Now... p is odd, and so is q, so r must be even. So r = 2k for some number k.

p-1 = qr = 2kq -> p = 2kq + 1

Which is the first half of our result.

Quote:
 This gives 2^[(p-1)/2] = 2^qk = 1 (mod p)
(p-1)/2 = 2kq/2 = kq, and 2 to any multiple of q is congruent to 1 mod p because q is the order of 2 (mod p)

Quote:
 so 2 is a quadratic residue mod p
Woops, I forgot to mention quadratic residues. Saying that 2 is a quadratic residue (mod p) means that at least one number x exists with the property x^2 = 2 (mod p).

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 left-hand side is even,
i.e. the LHS is a perfect square.

Quote:
 and it follows p = +/-1 (mod 8), which completes the proof.
This follows from another theorem I won't be explaining here.
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]   2002-09-14, 15:22 #3 Daffy   Aug 2002 31 Posts Great explanations. What propriety are you using to get this ? Mq + 1 = 1 (mod p) -> (2^q - 1) + 1 = 1 (mod p)   2002-09-14, 15:30   #4
toferc

Aug 2002

3010 Posts Quote:
 Originally Posted by Daffy Great explanations. What propriety are you using to get this ? Mq + 1 = 1 (mod p) -> (2^q - 1) + 1 = 1 (mod p)
The defintition of Mq is

Mq = 2^q - 1.

This is just a substitution step.   2002-09-14, 17:39 #5 asdf   Sep 2002 22×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.   2002-09-14, 18:05   #6
toferc

Aug 2002

2·3·5 Posts Quote:
 Originally Posted by asdf 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.
The only restriction on the number k is that it is a nonnegative integer. For example, M11 = 2^11 - 1 = 2047 has the divisors 1, 23, 87 and 2047.

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 &lt; 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) &lt; sqrt(2^p) = 2^(p/2)

2kp + 1 &lt; 2^(p/2)
2kp &lt; 2^(p/2)
kp &lt; 2^(p/2 - 1)
k &lt; 2^(p/2 - 1) / p

If you try 11, you get
k &lt; 2^(4.5) / 11 = (approx) 2.057 &lt; 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 &lt; 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.   2002-09-25, 13:16 #7 TTn   10001010010102 Posts Actually k is slightly influenced by Zsigmondy's theorum http://mathworld.wolfram.com/ZsigmondyTheorem.html  2002-09-25, 17:38 #8 ewmayer ∂2ω=0   Sep 2002 República de California 2·3·29·67 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 odd-prime 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 left-hand 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 factor-size bound by 75-80%. 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 probable-prime 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 probable-prime, we'd have to go ahead and see whether it divides Mq anyway.) -Ernst   2002-09-25, 22:56   #9
asdf

Sep 2002

22·3·5 Posts I have found this, but I am not sure about it (especially because it contains an error

Quote:
 If p==1 mod 4 then k==3 or 0 mod 4. If p==3 mod 4 then k==0 or 1 mod 4 This gives us a nice try 2, skip 2 type pattern, so all that we have to do is set the initial value the factor, then add 2p or 4p according to the pattern.
Now, the 4p in that last part should be 6p. Is this statement correct? I am guessing in your statements that you say that p = 2qk+1, and this quote says that p is the exponent of the Mersenne.   2002-09-26, 02:00   #10
toferc

Aug 2002

1E16 Posts Quote:
 Originally Posted by ewmayer 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
Woops ops:. I can't believe I said that.

Thank you for clearing that up.

Tofer   2002-09-26, 04:46   #11
binarydigits

Aug 2002

648 Posts Quote:
 Originally Posted by toferc Woops. I can't believe I said that. Thank you for clearing that up.
Yes, you have to watch what you say around here. Any mistakes WILL be pointed out. I ought to know :?   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post UberNumberGeek Factoring 51 2017-02-13 20:30 siegert81 Math 23 2014-03-18 11:50 devarajkandadai Miscellaneous Math 15 2012-05-29 13:18 devarajkandadai Miscellaneous Math 6 2006-01-04 22:44 Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 03:52.

Sat Oct 16 03:52:05 UTC 2021 up 84 days, 22:21, 0 users, load averages: 0.73, 0.97, 1.03