20031217, 17:21  #1 
Dec 2003
Belgium
5×13 Posts 
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 20031223 at 19:32 
20031217, 22:22  #2  
Aug 2002
Portland, OR USA
2×137 Posts 
Re: help with the math
Quote:
So I gave in and went to Mersenne divisors Quote:
q = 2kp + 1 "q1 must be an even multiple of the order of 2 (mod q), which is p." > q1 = 2kp. 

20031218, 01:12  #3 
Dec 2003
Belgium
5·13 Posts 
What is meant by ''the order of 2''?
michael 
20031218, 03:44  #4  
"Gang aft agley"
Sep 2002
2·1,877 Posts 
Quote:
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 a^{m} = 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 20031218 at 03:45 

20031222, 22:26  #5 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
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 N1, i.e. we can always find an integer b (a socalled primitive root of order N1) such that b^(N1) == 1 modulo N, but b^((N1)/k) !== 1 modulo p for all k >1 which divide (N1). (Such exponents (N1)/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 q1, and thus p must divide q1. By Fermat's Little Theorem the order of 2 also divides q1, so q1 = 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 q1. However, it's easy to see that for p > 2, p must divide q1 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. 
20031223, 01:07  #6  
Aug 2002
Portland, OR USA
2×137 Posts 
Quote:


20031223, 16:10  #7 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
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 righthand 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 nonunity. 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 q1, and thus 2*p must divide q1. 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 20031223 at 19:04 
20031223, 18:49  #8 
Dec 2003
Belgium
5·13 Posts 
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 
20031223, 19:05  #9  
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
Quote:
Last fiddled with by ewmayer on 20031223 at 19:06 

20031223, 19:24  #10 
Dec 2003
Belgium
5·13 Posts 
'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 
20031223, 19:31  #11 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
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 smallestfactor 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
factoring special form of 1024bit RSA key  Johnatan  YAFU  20  20160422 04:33 
Number of distinct prime factors of a Double Mersenne number  aketilander  Operazione Doppi Mersennes  1  20121109 21:16 
Factors with special form  RedGolpe  Factoring  5  20111103 18:38 
Fermat number factors  Citrix  Math  35  20070123 23:17 
Closed form solution of x^2 = 2 mod Fermat number  mpenguin  Factoring  10  20050929 07:46 