3
$\begingroup$

The Wikipedia Page on Fermat numbers states that $F_5$ was "fully factored" in 1732. This appears to be the same time that Euler found that any factor of a Fermat number $F_n$ was of the form

$$2^{n+1}k+1$$

for some $k$ (later improved by Lucas) and found the smaller factor of $F_5$, the prime $641$, by trial and error. What isn't clear to me is whether Euler also verified that the larger factor $F_5 / 641 = 6,700,417$ was prime (it is).

C. Edward Sandifer's book How Euler did Even More contains the passage

Euler did not speculate in print on whether the other factor, 6,700,417, is prime. It is prime, but there is no evidence that Euler ever tried to find out.

but continues along the lines of how easy it is to prove, using the same tools Euler used to find the smaller factor.

You can't say a number is "fully factored" until you know all of its factors are prime.

I was originally going to ask whether Euler proved $6700417$ was prime, but in light of the above passage, I guess we'll never know.

Can we really say that $F_5$ was fully factored in 1732, or is there some date for the verification of $6700417$ that's more appropriate?

(user6530 pointed me to a cleaner version of the text than the Euler Archive preprint I'd originally linked to.)

$\endgroup$
  • $\begingroup$ I think here you will find the answer, long story short: we don't know, someones say yes, someones say no. Anyway, only six divisions are required to prove 6700417 is prime (plus a little theory, of course...) $\endgroup$ – user6530 Apr 13 at 16:22
  • $\begingroup$ @user6530 That's exactly the same text as in the PDF; I guess EA just had a preprint. So Wikipedia is still making a shaky claim. But somebody proved that number prime. $\endgroup$ – Spencer Apr 13 at 16:26
  • $\begingroup$ I think we cannot say more than this. In 1861 Zacharias Dase realized a tables of all primes up to 9000000, before (~1842) Crelle a table of primes up to 6000000. So 1861 is for sure the "terminus ante quem" 6700417 was proved to be a prime. $\endgroup$ – user6530 Apr 13 at 16:33
  • 3
    $\begingroup$ Actually, with the typical use of words, since 641 and 6,700,417 are primes and Euler factored it into them, then it was "fully factored" even if he did not know that either one was prime. Doing something does not require knowing that it was done. Of course, that is of interest in itself. $\endgroup$ – Conifold Apr 13 at 17:58
  • 2
    $\begingroup$ It was definitely not Fermat. He conjectured in a letter to de Bessy that Fermat numbers were all primes after testing the first four (at least, he did not blame it on the margins this time), which may be in the running for the worst famous conjecture ever. Not only is the next one composite, but no other prime among them turned up to this day. Leibniz, perhaps, but the convention is that one has to publicize it to get the credit. And it was Euler who took it upon himself to systematically decide Fermat's claims one way or the other, so he was likely the first. $\endgroup$ – Conifold Apr 13 at 19:44
0
$\begingroup$

Once you know that factors of $F_5$ must be of the form $64k+1$, then it is very easy to try all of the possible factors of 6700417. You need try $64k+1$ for $k\le 40$. You can easily use Sieve of Eratosthenes to eliminate at least some non prime numbers. For example eliminating numbers that are divided by 3,5,7,11 you left only with sixteen possible values for $k$: 3,4,7,9,10,12,15,18,22,24,25,30,33,37,40. It took for me less than two minutes to try one of the number using only paper and pencil and about half an hour to try all these numbers (hint: it is useful to use base 64 arithmetic). So, even Euler never claimed that 6700417 is prime, we can be almost sure that he knew it. And even if he didn't test it, it would be a simple exercise for his readers.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.