# How did Euler prove the Mersenne number 2^{31}-12^{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”?

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

Since $2^{32}\not\equiv 2\pmod {311}$, we know that $2^{31}-1$ is not divisible by $311$.