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

Answer

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.

Attribution
Source : Link , Question Author : SwimBikeRun , Answer Author : Thomas Andrews

Leave a Comment