mersenneforum.org  

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

Reply
 
Thread Tools
Old 2003-12-17, 17:21   #1
michael
 
Dec 2003
Belgium

10000012 Posts
Default Special Form of Mersenne and Fermat Number Factors

I finally had access to my email so i could activate my account here. I hope to get more respons here than in the information forum. I've searched online to proofs but they all seem to go easy over this, perhaps it is trivial to some of you, perhaps it should be to me too, but i just don't see it:

If a prime q devides Mp then follows:
2^p - 1=nq (1)
From fermat's little theorem we have:
2^p=2modp equivalent with 2^p - 1=1modp or
2^p - 1=kp + 1 (2)

(1)+(2)-->nq=kp + 1 but how do i conclude now that q=k'p+1?

-michael

Last fiddled with by ewmayer on 2003-12-23 at 19:32
michael is offline   Reply With Quote
Old 2003-12-17, 22:22   #2
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default Re: help with the math

Quote:
Originally posted by michael
If a prime q devides Mp then follows:
2p - 1=nq (1)
From fermat's little theorem we have:
2p = 2 mod p equivalent with 2p - 1 = 1 mod p or
2p - 1 = kp + 1 (2)

(1)+(2)-->nq=kp + 1 but how do i conclude now that q=k'p+1?
I tried to go from there to q = 2kp + 1, but I also got lost.

So I gave in and went to Mersenne divisors
Quote:
(Note: Chris Caldwell uses p & q in swapped positions, so I switched them back.)
If q divides Mp, then 2p = 1 (mod q) and the order of 2 (mod q) divides the prime p, so it must be p.

By Fermat's Little Theorem the order of 2 also divides q-1, so q-1 = 2kp.
q - 1 = 2kp
q = 2kp + 1

"q-1 must be an even multiple of the order of 2 (mod q), which is p." --> q-1 = 2kp.
Maybeso is offline   Reply With Quote
Old 2003-12-18, 01:12   #3
michael
 
Dec 2003
Belgium

5·13 Posts
Default

What is meant by ''the order of 2''?

-michael
michael is offline   Reply With Quote
Old 2003-12-18, 03:44   #4
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

EAA16 Posts
Default

Quote:
Originally posted by michael
What is meant by ''the order of 2''?

-michael
I think this is a reference to the order of a group. Someone with more math than I know will surely answer more completely (and more correctly!)

Looking at my copy of A Survey of Modern Algebra by Garrett Birkhoff and Saunders Mac Lane:
The order of an element a in a group is the least positive integer m such that am = e; if no positive power of a equals the identity e, a has the order infinity.

So, I would take it to mean that "the order of 2 (mod q)" is the least integer that 2 would be raised to to be equal to 1 (mod q).

Last fiddled with by only_human on 2003-12-18 at 03:45
only_human is offline   Reply With Quote
Old 2003-12-22, 22:26   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2·5,791 Posts
Default

Correct - the order of 2 modulo p is the least power to which we need to raise 2 to get back 1, modulo p. It can be shown that arithmetic modulo a prime N defines a group of order N-1, i.e. we can always find an integer b (a so-called primitive root of order N-1) such that b^(N-1) == 1 modulo N, but b^((N-1)/k) !== 1 modulo p for all k >1 which divide (N-1). (Such exponents (N-1)/k are the only possible ones to which we can raise an integer > 1 and get back 1 modulo N - that is what we mean when we say that the order of any element must divide the group order.)

Now let's look more closely at the following statements:

If q divides M(p), then 2^p = 1 (mod q)

This is just another way of saying that q divides M(p) = 2^p - 1. In terms of our group terminology, it also says that...

...the order of 2 (mod q) divides the prime p, so it must be p.

If q is a proper factor of M(p) (i.e. q is prime), then the group (specifically we mean a multiplicative group in all of this discussion) defined by arithmetic modulo q has order q-1, and thus p must divide q-1.


By Fermat's Little Theorem the order of 2 also divides q-1, so q-1 = 2kp.

Perhaps I'm missing something here, but the extra factor of 2 does not immediately follow from FLT. This appears to simply restate what we just established above, namely that p divides q-1. However, it's easy to see that for p > 2, p must divide q-1 an even number of times: since p is prime > 2 it must be odd. Also, we've already established that q > p , so q is also an odd prime. Writing q = j*p + 1, we see that for p odd, j must be even, otherwise q is even, hence not prime. Thus j = 2*k.

The case p = 2 can be dealt with by other means.
ewmayer is offline   Reply With Quote
Old 2003-12-23, 01:07   #6
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

1000100102 Posts
Default

Quote:
Originally posted by ewmayer
Perhaps I'm missing something here, but the extra factor of 2 does not immediately follow from FLT.
Yes, he does slip that 2 in there. Perhaps he figures it is "obvious". Since I was quoting him, I couldn't add the extra step for clarification. Probably I should have done more than put the word "even" in my summary line.
Maybeso is offline   Reply With Quote
Old 2003-12-23, 16:10   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×5,791 Posts
Default

One can use the same kind of argument to establish the similar special form the factors of Fermat numbers F(n) = 2^(2^n) + 1 must have. To simplify the notation let's let p = 2^n, where in this case p is most definitely not prime - I only use it to show how similarly the Mersenne and Fermat cases proceed.

Now, if q divides F(n), then 2^p == -1 (mod q). (Note the sign change of the right-hand side term!) Since we have -1 intead of a +1 on the RHS, 2 is not a root of unity of order p, and we can't yet say anything based on group orders. However, if we square the above we see that 2^(2*p) == +1 (mod q), i.e. 2 is a root of order 2*p, or equivalently, a modular square root of order p.

Now, the fact that 2^p == -1 and 2^(2*p) == +1 (mod q) says more - it says that in fact 2 is a primitive root of order 2*p. We can think of a primitive root r of any order O as being a root that has the full order O, in the sense that raising r to any power < O returns non-unity. How does the fact that 2^p == -1 allow us to conclude that 2 is a primitive root of order 2*p? Well, the only powers of 2 that can possibly yield a unity result are those which divide the group order 2*p. Any such smaller power must also divide p. So if there existed a power x < 2*p for which 2^x == +1 (mod q), that would imply that also 2^p == +1 (mod q), which we know not to be true. This is crucial in this instance, because the fact that p is composite doesn't allow us to make a statement like for the Mersennes:

...the order of 2 (mod q) divides the prime p, so it must be p.

Instead we have directly established that the order of 2 (mod q) is 2*p, because the fact that 2^p == -1 (mod q) implies that the order of 2 is greater than p. Thus, we continue as for the M(p):

If q is a proper factor of F(n), then the group defined by arithmetic modulo q has order q-1, and thus 2*p must divide q-1. Since 2*p = 2*2^n = 2^(n+1), Fermat number factors must have the form q = j*2^(n+1) + 1.

In this case, because the term multiplied by j is even rather than odd, we cannot conclude that j is a multiple of 2 based on a simple parity argument. The great Edouard Lucas (yep, that Lucas) was the first to show j is in fact itself even, i.e. Fermat factors have form k*2^(n+2) + 1; when I get a chance to look up his proof of that fact I'll add it to this post if it's sufficiently simple to follow.

Last fiddled with by ewmayer on 2003-12-23 at 19:04
ewmayer is offline   Reply With Quote
Old 2003-12-23, 18:49   #8
michael
 
Dec 2003
Belgium

5·13 Posts
Default

If i understand this correct you state Fermat numbers areF(n)= 2^p + 1 where p=2^n and construct a factor which must have the form q = j*2^(p+1) + 1. I must congratulate you on finding factors that are bigger than the initial number itself...or am i missing something again!!?

I would expect a divisor to be of the from q=j*p+1 like 2^32+1=0mod641 (p=2^5) and 641=5*2*32+1, where j is 10=0mod2, i'll try to see if i can figure out why j=0mod2.

-michael
michael is offline   Reply With Quote
Old 2003-12-23, 19:05   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×5,791 Posts
Default

Quote:
Originally posted by michael
If i understand this correct you state Fermat numbers areF(n)= 2^p + 1 where p=2^n and construct a factor which must have the form q = j*2^(p+1) + 1.
That should have (and now does) read q = j*(2*p) + 1 = j*2^(n+1) + 1, obviously.

Last fiddled with by ewmayer on 2003-12-23 at 19:06
ewmayer is offline   Reply With Quote
Old 2003-12-23, 19:24   #10
michael
 
Dec 2003
Belgium

6510 Posts
Default

'641=5*2*32+1' aarghh to myself ... 641=10*2*32+1

or for q = j*(2*p) + 1;
q=641
p=2^5
j=10

-michael
michael is offline   Reply With Quote
Old 2003-12-23, 19:31   #11
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×5,791 Posts
Default

Another interesting consequence of the special form of Mersenne and Fermat nunber factors is that it points up the fallacy of extrapolating from small examples ("F(0)-F(4) are all prime, therefore all F(n) must be prime.")

For Mersennes M(p), since any proper smallest-factor q must satisfy the dual properties that

1) q > 2*p

2) q < sqrt(M(p)) ,

For M(p) to possibly be composite we require that 2*p < sqrt(M(p)). The smallest prime for which this is true is p = 11, and this happens to also be the first composite M(p).

For F(n) to possibly have a factor a similar criterion must hold, namely that 2^(n+2) < sqrt(F(n)). The smallest n for which this inequality is satisfied is n = 4, and F(4) is still prime. However, there are only 3 q's of the proper form (65, 129, 193) which are also < sqrt(F(4)) ~= 256, and only one of these is actually prime, so in fact F(4) has just one possible candidate factor, and it should come as no huge surprise that this single candidate happens to not pan out. The very next F(n), F(5), has factor candidates 129, 257, 385, 513, 641, ... . We can throw out 129, 385 and 513 as these are all composite. 257 is itself a Fermat number (F(3)), and it's easy to show that no Fermat number can divide another. So the first true factor candidate is 641, and that happens to be a factor of F(5). In this light, the fact that F(0)-F(4) are all prime is not at all surprising.
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factoring special form of 1024-bit RSA key Johnatan YAFU 20 2016-04-22 04:33
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
Factors with special form RedGolpe Factoring 5 2011-11-03 18:38
Fermat number factors Citrix Math 35 2007-01-23 23:17
Closed form solution of x^2 = 2 mod Fermat number mpenguin Factoring 10 2005-09-29 07:46

All times are UTC. The time now is 06:54.

Wed Jan 20 06:54:10 UTC 2021 up 48 days, 3:05, 0 users, load averages: 3.34, 3.42, 3.49

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.