Mersenne: Re: Mersenne and Fermat

[EWMAYER]

[There appears to be a problem with the mailing list. In an effort
to help Gordon Irlam track it down, I am attempting to resend this
message, which I first attempted to post last week.          -EWM]

Hi, David:

David Sanders <[EMAIL PROTECTED]> wrote:

>> Mersenne primes are especially interesting to me.  Just through simple
>>observation I found the relationship
>>
>>              If p is a prime, then p evenly divides 2^(p-1)-1
>
>Of course, that should have read "If p is an odd prime..."
>
>It has been interesting.  I haver received a number of replies, but they are
>baffling me.  About half of the replies offer some help in a proof of the theorem,
>and the other half deny the truth of the theorem, sometimes even giving
>counterexamples.

By now you know this is Fermat's "little" theorem, first proved by Euler over
300 years ago (about 50 years after Fermat first stated it.)

>Now, the counter examples offered are not counter examples at all, and the
>theorem holds (except for p=2).

Since the theorem has been proven, there are no counterexamples. What
*is* true (and this may have confused some of your repliers) is that the
CONVERSE OF THE THEOREM NEED NOT HOLD, i.e. not every
odd p which divides 2^(p-1) - 1 is a prime, though the overwhelming
majority of them are. As an example of such a composite number (ones
which pass the base-2 Fermat test are known as base-2 Fermat pseudoprimes),
try p = 561. This particular p is also a "Carmichael Number," meaning that
it is not only a pseudoprime to base 2, but also to every eligible base for
which we can make the Fermat test for this p, i.e. it divides a^(p-1) - 1
for every a which is relatively prime to 561 (has factors in common with 561).

(Aside: we probably shouldn't be using "p" in our notation here, since
in a number-theoretical context that often implies a prime, which
e.g. 561 is not.)

See also

http://mathworld.wolfram.com/CarmichaelNumber.html


>So it appears that for some reason I have not communicated this idea very
>well.   I have since learned that this is essentially Fermat's Little Theorem.
>The most troubling thing to me is that apparently the members of the list
>aren't even using the same language -- otherwise I would not have gotten
>the contradictory replies I have.

A huge variety of people read the list, from nonmathematicians to
top-flight number theorists (though the latter tend to contribute
lees often.)

>Also, I had thought that this was a list for public discussion, and yet I have
>not received even one replie via the list -- or do the headers hide the fact
>that the reply is from the list?

I can't speak for others, but several recent messages I've attempted
to send to the list have gotten bounced by an apparently overactive
spam filter. I sent e-mail to Gordon Irlam (the list admin) about this,
but have not yet gotten a satisfactory explanation (one of my posts
that got bounced contained the string "xxx", but after changing it to yyy
and resubmitting, it still didn't get through). I'm mailing a copy
of this directly to you, so you'll get it even the list doesn't.

>I am greatly perplexed!

I hope I managed to slightly lessen your perplexity.

Cheers,
-Ernst