I read that Euler proved $2^{31} -1$ is prime. What techniques did he use to prove this so early on in history? Isn't very large number stuff done with computers? Do you know if Euler had a team of people to follow algorithms for him, dubbed "computers"?
$\begingroup$
$\endgroup$
7
asked Mar 22, 2013 at 15:27
-
13$\begingroup$ $2^{31}-1$ isn't that large - it is about $2$ billion. $\endgroup$– Thomas AndrewsMar 22, 2013 at 15:30
-
2$\begingroup$ Proving that $n=31=2^5-1$ is a Mersenne prime is not hard at all. However, proving that $2^{31}-1$ is prime... That's another story. My point: you should fix the title. $\endgroup$– Álvaro Lozano-RobledoMar 22, 2013 at 15:33
-
13$\begingroup$ François Arago once said of Euler "He calculated without any apparent effort, just as men breathe, as eagles sustain themselves in the air." $\endgroup$– Alex J BestMar 22, 2013 at 15:33
-
1$\begingroup$ They didn't compute every single possibibility, like we would do with a computer nowadays. Note that some mersenne numbers were found before smaller ones. For example, $M_{127}$ was found to be prime before $M_{61}$, $M_{89}$ and $M_{107}$. So they probably did it in a different way. Read this: en.wikipedia.org/wiki/Mersenne_prime for some primality tests on mersenne numbers. $\endgroup$– MyUserIsThisMar 22, 2013 at 15:34
-
$\begingroup$ Even with exhaustive divisibilty testing (sieve of Erastothenes) there is no need to try divisors larger than $\sqrt n$, or 46340, and only prime numbers in that space are candidates. This space is not so much work to test, especially if you have students. Right off the bat we can eliminate all even numbers, and those divisible by three, leaving only around 15,450 numbers to test. Multiples of 2 and 5 are distinguished by their least significant decimal digit and multiples of three are easily recognized and eliminated. If a list of prime numbers below 46340 is available, it's even easier. $\endgroup$– KazMar 23, 2013 at 2:49
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
13
No, Euler did not require a team for this sort of problem, he could greatly simplify the calculations necessary by hand using some mathematical reasoning. (According to commenter MathGems below, he had assistants, but even then, it seems like an urban legend to say that he called them "computers." Certainly, it was unlikely to be an English word, although he might have chosen the French equivalent.)
Did he use one assistant or more for this calculation? Pretty much impossible to tell. Would he need a team of people crunching away in a back room to do this particular calculation? No.
If $q$ is a prime factor of $2^p-1$ then $2^p\equiv 1\pmod q$ and hence $p|q-1$, so $q\equiv 1\pmod p$. That means, roughly, when $p=31$, that you only have to check about one out of every $31$ primes.
You can also conclude that $q\equiv \pm 1\pmod 8$, since $$2\equiv 2^{p+1} \equiv \left(2^{\frac{p+1}{2}}\right)^2\pmod q$$ so $2$ must be a square modulo $q$. This reduces roughly in half again the possible values for $q$.
Together, these mean that $q\equiv 63$ or $q\equiv 1\pmod {8\cdot 31=248}$. The smallest possible such $q$ is $311$. The next is $q=1303.$ As you can see, this is going to greatly reduce the amount of checking we have to do.
Now, with $n=2^{31}-1$ you only have to check prime factors up to $\sqrt{2^{31}-1}<46341$. A crude estimate says that we should expect approximately $70$ primes in this range which satisfy the above conditions. (The exact count is $84.$)
Also, it is not necessary to actually divide $2^{31}-1$ by $q$ to prove that it doesn't divide. Rather, you can compute $2^{32}\pmod q$ by repeated squaring. For example, if $q=311$:
$$2^2\equiv 4\pmod {311}$$ $$2^4\equiv 4^2 \equiv 16\pmod {311}$$ $$2^8 \equiv 16^2 \equiv 256\equiv -55\pmod {311}$$ $$2^{16}\equiv (-55)^2 \equiv -85\pmod{311}$$ $$2^{32}\equiv (-85)^2\equiv 72\pmod {311}$$
Since $2^{32}\not\equiv 2\pmod {311}$, we know that $2^{31}-1$ is not divisible by $311$.
answered Mar 22, 2013 at 15:40
-
$\begingroup$ Should the 2 on the last line be a 1, or am I being silly? $\endgroup$ Mar 22, 2013 at 15:58
-
2$\begingroup$ There are several $2$s in the last line, @AlexJBest. Since I computed $2^{32}$ because it was easier than computing $2^{31}$, I was using that $311|2^{32}-2$ if and only if $311|2^{31}-1$ $\endgroup$ Mar 22, 2013 at 16:03
-
-
$\begingroup$ Very nice. So in fact the actual computation could be carried out in an hour or two by a patient schoolchild. Certainly it wouldn't require a team of human computers. $\endgroup$ Mar 22, 2013 at 16:56
-
2$\begingroup$ But Euler did have a team. For example if you read Weil's Number theory, an approach through history you will encounter at least 15 passages mentioning Euler's "assistants" (which included Euler's son, Nicolas Fuss, and folks sent from Basel with the cooperation of Daniel Bernoulli). The assistants presumably played a large role after Euler became blind (circa 1771). $\endgroup$ Mar 22, 2013 at 18:40
$\begingroup$
$\endgroup$
6
Euler proved $\rm\: M_{31}= 2^{31}\!-1\:$ is prime by showing that all prime divisors are $\rm\equiv 1$ or $\rm\, 63\:\ (mod\ 248),\:$ then test dividing by all primes of this form below $\rm\sqrt{M_{31}}.\:$ The constraint on the prime divisors is an immediate consequence of the (now) well-known Mersenne factor theorem: for odd primes $\rm\:p,q,\:$ $\rm\: p\mid M_q\:\Rightarrow\: p\equiv 1\,\ (mod\ q),\,\ p\equiv \pm 1\,\ (mod\ 8).\:$
Below is an excerpt from his 1772 letter to Bernoulli describing this. See also this page.
-
11$\begingroup$ «Ces règles sont fondées sur un principe dont la démontration n'est pas encore connue.» Pure genius :-D $\endgroup$ Mar 22, 2013 at 16:14
-
1
-
9
-
1$\begingroup$ "These rules are based on a principle which demontration is not yet known" $\endgroup$ Mar 27, 2013 at 3:07
-
$\begingroup$ doesn't it say that Fermat had already proved that $2^{31}-1$ is a prime? $\endgroup$– AntSep 28, 2014 at 15:40
$\begingroup$
$\endgroup$
5
Euler did not use a team to calculate all possible prime divisions, however he may have used assistants to do routine calculations (see comments and other answers). He was however very very clever and I have no doubt that he could himself have performed the necessary calculations incredibly fast. As I mentioned in the comments François Arago said "He calculated without any apparent effort, just as men breathe, as eagles sustain themselves in the air." He noticed some properties primes dividing $2^{31}-1$ must have, which reduced the calculation required immensely. Full details are here.
answered Mar 22, 2013 at 15:40
-
8$\begingroup$ «Very very clever» is quite an understatement regarding Euler :-) $\endgroup$ Mar 22, 2013 at 16:13
-
1
-
1$\begingroup$ I don't know what this means: "Euler had no team" - he was a professor and was teaching, so he had students and if I'm not recalling my readings completely false, they've let their students and assistents do standard calculations. Well, remarks about things like that occur sometimes as sidenotes or half-sentences in biographies - but I think, it should have been some common behave (at least I'd have done it this way if I'd lived in that era) $\endgroup$ Mar 22, 2013 at 19:12
-
$\begingroup$ Ahh apologies, I did not know about this! $\endgroup$ Mar 22, 2013 at 19:22
-
5$\begingroup$ You know, maybe Euler wasn't all that clever. He just developed his potential more fully by not wasting his time surfing the web, answering e-mails, driving two hours a day in rush hour traffic, or sinking time into crap like Unix, MS Windows, LaTeX, Mathematica, ... $\endgroup$– KazMar 23, 2013 at 3:08