 mersenneforum.org > Math Special Form of Mersenne and Fermat Number Factors
 Register FAQ Search Today's Posts Mark Forums Read  2003-12-17, 17:21 #1 michael   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 2003-12-23 at 19:32   2003-12-17, 22:22   #2
Maybeso

Aug 2002
Portland, OR USA

2×137 Posts 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.   2003-12-18, 01:12 #3 michael   Dec 2003 Belgium 5×13 Posts What is meant by ''the order of 2''? -michael   2003-12-18, 03:44   #4
only_human

"Gang aft agley"
Sep 2002

2×1,877 Posts 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   2003-12-22, 22:26 #5 ewmayer ∂2ω=0   Sep 2002 República de California 2×5×7×167 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 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.    2003-12-23, 01:07   #6
Maybeso

Aug 2002
Portland, OR USA

2·137 Posts 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.   2003-12-23, 16:10 #7 ewmayer ∂2ω=0   Sep 2002 República de California 2DAA16 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 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   2003-12-23, 18:49 #8 michael   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   2003-12-23, 19:05   #9
ewmayer
2ω=0

Sep 2002
República de California

101101101010102 Posts 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   2003-12-23, 19:24 #10 michael   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   2003-12-23, 19:31 #11 ewmayer ∂2ω=0   Sep 2002 República de California 101101101010102 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 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.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Johnatan YAFU 20 2016-04-22 04:33 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 RedGolpe Factoring 5 2011-11-03 18:38 Citrix Math 35 2007-01-23 23:17 mpenguin Factoring 10 2005-09-29 07:46

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

Tue Jan 25 10:05:23 UTC 2022 up 186 days, 4:34, 0 users, load averages: 1.40, 1.71, 1.49