There is a simple proof without using quadratic thingies.
The prime f divides a^(f-1)-1 /* Fermat's Little Theorem */
It may first divide a Mersenne number with a smaller exponent,
call it a^E-1 and then all exponents that are multiples of E,
one of which equals f-1, let's call it EK = f-1.
(f-1) is even, call it 2kE. So for E to be odd and f | a^E-1
then f=2kE+1.
Indeed all the powers of 2 that are factors of f-1 must "drop",
so f=(2^m)kE+1 for all odd E and all bases that f doesn't divide.
Similarly for Fermat divisors, all the other factors of f-1 must
"drop" leaving only powers of 2.
In base 2 using quadratic residues (whatever they are :-) gives
us the 1 or 7 mod 8 for divisors of 2^p-1.
Does anyone have any (more) heuristics for the probabilistic
distribution of K or 2^m.k, where E=(f-1)/K ??
My shot in the dark is that it is less likely for an f=1 (mod 8)
to "drop" 3 powers of 2 and divide 2^E-1 with an odd exponent, E
than it would be for another f=7 (mod 8) to "drop" only one.
Pr�st,
Paul Landon
> From: Alexander Kruppa
> Subject: Re: Mersenne: smallest possible factor
>
> Spike Jones wrote:
>
> > A few weeks ago, I thought someone posted something like:
> >
> > 2^n-1 where n is prime cannot have any factor smaller than n.
> >
> > Did I get that right? Is there a simple proof? spike
>
> Factors of a mersenne number Mp are always of the form f=2*p*k+1, k may be
> as small as 1.
> The proof that factors are 2kp+1 is not simple as far as I remember and uses
> the theory of quadratic residues (and thus I didn't understand it). See it
> on Chris Caldwells (superb) page on Prime numbers,
> http://www.utm.edu/research/primes/ .
> The proof is at http://www.utm.edu/research/primes/notes/proofs/MerDiv.html
>
> Ciao,
> Alex.
>
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
