mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2002-09-14, 00:09   #1
asdf
 
asdf's Avatar
 
Sep 2002

22×3×5 Posts
Default 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.
asdf is offline   Reply With Quote
Old 2002-09-14, 05:11   #2
toferc
 
Aug 2002

111102 Posts
Default

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]
toferc is offline   Reply With Quote
Old 2002-09-14, 15:22   #3
Daffy
 
Aug 2002

31 Posts
Default

Great explanations.

What propriety are you using to get this ?

Mq + 1 = 1 (mod p) -> (2^q - 1) + 1 = 1 (mod p)
Daffy is offline   Reply With Quote
Old 2002-09-14, 15:30   #4
toferc
 
Aug 2002

2×3×5 Posts
Default

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.
toferc is offline   Reply With Quote
Old 2002-09-14, 17:39   #5
asdf
 
asdf's Avatar
 
Sep 2002

22×3×5 Posts
Default

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.
asdf is offline   Reply With Quote
Old 2002-09-14, 18:05   #6
toferc
 
Aug 2002

2×3×5 Posts
Default

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 < 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.
toferc is offline   Reply With Quote
Old 2002-09-25, 13:16   #7
TTn
 

19×263 Posts
Default

Actually k is slightly influenced by Zsigmondy's theorum

http://mathworld.wolfram.com/ZsigmondyTheorem.html
  Reply With Quote
Old 2002-09-25, 17:38   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

100110011011012 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2002-09-25, 22:56   #9
asdf
 
asdf's Avatar
 
Sep 2002

6010 Posts
Default

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.
asdf is offline   Reply With Quote
Old 2002-09-26, 02:00   #10
toferc
 
Aug 2002

2·3·5 Posts
Default

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
toferc is offline   Reply With Quote
Old 2002-09-26, 04:46   #11
binarydigits
 
Aug 2002

22·13 Posts
Default

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 :?
binarydigits is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 factoring attempts at smallest-remaining Mersenne numbers with no known factors UberNumberGeek Factoring 51 2017-02-13 20:30
Modular restrictions on factors of Mersenne numbers siegert81 Math 23 2014-03-18 11:50
Mersenne prime factors of very large numbers devarajkandadai Miscellaneous Math 15 2012-05-29 13:18
Mersenne Prime Factors of v.large numbers devarajkandadai Miscellaneous Math 6 2006-01-04 22:44
Factors of Mersenne numbers ? Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 05:45.

Mon Nov 30 05:45:38 UTC 2020 up 81 days, 2:56, 3 users, load averages: 1.67, 1.48, 1.33

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