Factors of Mersenne Numbers

[asdf]

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.

[toferc]

I am assuming that you read the proof on Chris Caldwell's Prime Pages. I'll quote it:

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!

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)

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.

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

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.

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)

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.

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]

[Daffy]

Great explanations.

What propriety are you using to get this ?

Mq + 1 = 1 (mod p) -> (2^q - 1) + 1 = 1 (mod p)

[toferc]

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.

[asdf]

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.

[toferc]

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

Actually k is slightly influenced by Zsigmondy's theorum

http://mathworld.wolfram.com/ZsigmondyTheorem.html

[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

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

[asdf]

I have found this, but I am not sure about it (especially because it contains an error

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.

[toferc]

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

[binarydigits]

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