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

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

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.