# How did Euler prove the Mersenne number $2^{31}-1$ is a prime so early in history?

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"?

-
$2^{31}-1$ isn't that large - it is about $2$ billion. –  Thomas Andrews Mar 22 '13 at 15:30
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. –  Álvaro Lozano-Robledo Mar 22 '13 at 15:33
François Arago once said of Euler "He calculated without any apparent effort, just as men breathe, as eagles sustain themselves in the air." –  Alex J Best Mar 22 '13 at 15:33
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. –  MyUserIsThis Mar 22 '13 at 15:34
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. –  Kaz Mar 23 '13 at 2:49

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$.

-
Should the 2 on the last line be a 1, or am I being silly? –  Alex J Best Mar 22 '13 at 15:58
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$ –  Thomas Andrews Mar 22 '13 at 16:03
I am being silly, thanks! –  Alex J Best Mar 22 '13 at 16:04
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. –  Nate Eldredge Mar 22 '13 at 16:56
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). –  Math Gems Mar 22 '13 at 18:40

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).\:$

-
«Ces règles sont fondées sur un principe dont la démontration n'est pas encore connue.» Pure genius :-D –  Mariano Suárez-Alvarez Mar 22 '13 at 16:14
which language is this? –  user13107 Mar 22 '13 at 17:13
@user13107 French –  Dan Neely Mar 22 '13 at 17:29
"These rules are based on a principle which demontration is not yet known" –  Sandra West Mar 27 '13 at 3:07

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.

-
«Very very clever» is quite an understatement regarding Euler :-) –  Mariano Suárez-Alvarez Mar 22 '13 at 16:13
It was meant to be a bit of a joke :) –  Alex J Best Mar 22 '13 at 16:15
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) –  Gottfried Helms Mar 22 '13 at 19:12
Ahh apologies, I did not know about this! –  Alex J Best Mar 22 '13 at 19:22
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, ... –  Kaz Mar 23 '13 at 3:08