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

Re: help with the math
 

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

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

So I gave in and went to [URL=http://www.utm.edu/research/primes/notes/proofs/MerDiv.html]Mersenne divisors[/URL]
[quote][size=1] (Note: Chris Caldwell uses p & q in swapped positions, so I switched them back.)[/size]
If q divides Mp, then 2[sup]p[/sup] = 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.
[/quote]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.

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

-michael

[QUOTE][i]Originally posted by michael [/i]
[B]What is meant by ''the order of 2''?

-michael [/B][/QUOTE]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 [i]A Survey of Modern Algebra[/i] by Garrett Birkhoff and Saunders Mac Lane:
The order of an element [i]a[/i] in a group is the least positive integer [i]m[/i] such that [i]a[sup]m[/sup][/i] = [i]e[/i]; if no positive power of [i]a[/i] equals the identity [i]e[/i], [i]a[/i] 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).

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:

[i]If q divides M(p), then 2^p = 1 (mod q)[/i]

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

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

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


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

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

[QUOTE][I]Originally posted by ewmayer[/I]
[B]Perhaps I'm missing something here, but the extra factor of 2 does not immediately follow from FLT.[/B][/QUOTE] 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.

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 [i]primitive[/i] root of order 2*p. We can think of a primitive root r of any order O as being a root that has the [i]full order[/i] 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:

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

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, [i]that[/i] 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.

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

[QUOTE][i]Originally posted by michael [/i]
[B]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.[/B][/QUOTE]

That should have (and now does) read q = j*(2*p) + 1 = j*2^(n+1) + 1, obviously.

'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

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.