A Historic Question about Fermat

Gyan

Hope the moderators allow this unusual question here .. but something started troubling me...

If N=2^32+1

It is easy to see that 3^N is NOT 3 (moodulo N). and this requires only 32 squaring of the number 3 which is not hard. even without a calculator..

Yet why didn't Fermat know (after all it was his 'little' theorem and his prime) that this number is NOT prime.

Why it has too wait till Euler?
Something is strange here... how come Fermat did not notice it????

(PS- Move if this is not appropiate here in this form)

**Posted:** Mon Aug 09, 2004 2:17 pm

pbornsztein

Don't blame Fermat too hardly. The test of primality you are referring to is known as Pepin's test, and appeared in 1877. A little late for Fermat to know it...

There are many 'easy' results which have been discovered later after the tools needed to prove them have been elaborated.

Pierre.

**Posted:** Mon Aug 09, 2004 2:40 pm

Gyan

No , This is known much earllier then Pepin's test.

Pepin's test fails because [(3)^(2^16) == (-1) mod (F(5)] is untrue.

What I said was simply Fermat's little theorem eg:

3^N is NOT equal to 3 . (mod N)
And that means N is not prime

That 'little theoeem' was certainnly popularized by him and i assume known , by him., AND as said before, SIMPLE (I mean only 32 squarings are needed) enough for him to do.

Hope you see that... Whar am I missing?

That's what bothers me.

**Posted:** Tue Aug 10, 2004 8:56 am

Michael Lipnowski · Poincare Conjecture Offline Joined: 04 Mar 2004 Posts: 108

I sympathize with Fermat with respect to the $641|2^{32} + 1$ oversight.

The fact is that even without $\it relatively$ modern primality tests or even Fermat's Little Theorem, which presumably was popularized by Fermat, hence the name, there are simple ways of proving $641|2^{32}+1$ . After viewing this thread, I decided to search for one, and found this doozie:

$641 = 5*2^7 + 1 = 2^4 + 5^4$ . Therefore, $641|5^4 2^{28} + 2^{32}, 5^4 2^{28}-1$ , hence, $641|2^{32}+1$ , their difference.

On the other hand, in Fermat's defence, he was a brilliant mathematician. If he were posed the problem of proving that $641|2^{32} + 1$ , I don't doubt that he would have proven it elegantly. But $641$ isn't exactly a prime that comes to mind immediately (at least it wasn't at the time Wink

) when testing for primality; it took a calculation savant like Euler to spot it, only so that we all can take cheap shots at Fermat for missing it. And even if Fermat searched for primes as large as $641$ , which we'll never know for certain, there are so many small primes to check that he probably didn't exert a whole-hearted effort to prove divisibility, or non-divisilbity, by most of them.

**Posted:** Wed Aug 11, 2004 10:31 pm

Gyan

Michael -

I think yoiu are missing the point. It is NOT hindsight/20-20 type of reasoning ... and no one is taking a cheap shot at Fermat that he missed 641.

The point was, if applied his own FLT, it was sure, and he would know for sure that he did NOT have to do MORE THAN 32 squaring.. which I believe is not too much not to expect from him...(After all simplest Primality tests depend on this so one can easily rule out a given large number as not prime by this test without having to find a factor)

It is NOT a case of him NOT trying all little primes etc... it is a case of him not doing a 32 step process which he ought to have known that it would not take long. .

******* New Thought ****

Now going of on a tangent .. and it is not directly related to the above, but Euler (who understood FLT) not only found out the number is not prime, but its factor also. He did not have to search through all the little primes though .. it can be easily proven that if F(5) had factors all have to be of the form:
128*k + 1 or 129, 257, 385, 513,..641.. etc and if you disallow 129,385,513 .. etc (They are not prime) .. to find 641 was not that hard. .It was the next number after 257...

Note that I am not blaming Fermat for not deducing that he only has to try prime factors of the type 128K+1 (though it is not hard to prove it now.. and that is what helped Euler).

PS - BTW the FLT test for prime is not new.. Specially afeter Euler.. mathematicians routinely used it to show and know some numbers (2^n-1 types) as non-prime though they did not know their factors...

**Posted:** Tue Aug 17, 2004 11:57 am