On the Wikipedia page there is an ordered list of Mersenne primes and the dates they were discovered. The largest such primes and most recent discoveries were made with the help computers. But the largest Mersenne prime discovered without computer aid is $2^{127}-1$ by $\acute{\text{E}}\text{douard Lucas}$ in 1876, which has more than $38$ digits.
$2^{127}-1 = 170141183460469231731687303715884105727$.
How can one prove that such a large number is prime without the help of a computer?
Food for thought:
$2^{127}-1$ where $127= 128 -1=2^7-1$ where $7=8-1 =2^3-1$ where $3=4-1=2^2-1$.
Best Answer
We sometimes underestimate the capability and perseverance that mathematicians had in those times, the age of no calculator, just calamo charta.
Edouard Lucas discovered that $M_{127}$ was prime. However, contrary to what may be popularly thought, he did not use the Lucas-Lehmer test!
Indeed, Lucas only knew that his test which he had devised in 1856, was sufficient, and that too only for certain values of the exponent. The Lucas-Lehmer test was not fully proved until Lehmer came along in 1930 and proved it.
Indeed, the result used by Lucas was one that he supposed true : it was not given a rigorous proof until 1913 by Carmichael, but was considered a true statement at the time of Lucas' computation.
Let $F_k$ denote the $k$th Fibonacci number, and let $n \in \mathbb N$. Then $n$ is a prime number if :
and similarly $n$ is a prime number if :
Since $2^{127}-1 \equiv 7 \pmod{10}$ (which does not require great computation capacity!) we can apply the first test. Indeed, note that $n+1 = 2^{127}$, so all(!) we have to verify is that $2^{127}-1$ divides $F_{2^{127}}$ but not $F_{2^m}$ for any $1\leq m \leq 127$.
Which Lucas did, using ideas that eventually led to the Lucas-Lehmer test : in other words, the Fibonacci and Lucas numbers satisfy the relation $F_{2n} = L_nF_n$ and $L_{2n} = L_n^2 -2 (-1)^n$ so one can get $(F_{2n},L_{2n})$ from $(F_{n},L_n)$! Furthermore, these respect modulo rules as well, and thus the computation is made simpler.
It also helped that Lucas had his own work to fall back on : he already had prime factorizations of the first sixty Fibonacci numbers , all his hard work.
Prior to Lucas' work, different methods were used to show primality (and non-primality!). Let's take $M_{31} = 2^{31}-1$. This was not shown prime by the Lucas-Lemher test. Indeed, it came with a startling observation by Euler :
I would like to know how he proved this particular assertion, but all I can say is that it comes down to primes dividing forms of certain kinds. For a simple exercise, try to prove that if a prime $p$ divides a number of the form $x^2 - 2y^2$ then $p \equiv \pm 1 \pmod{8}$.
Following this observation, Euler proceeded to roughly compute $\sqrt{M_{31}} \approx 46340$ and then used a prime table to find all primes which were congruent to $1$ or $63$ modulo $248$ and see if they divided $M_{31}$. No such prime was found. $M_{31}$ is prime!
An extension of this observation was made by Landry : Let $n \in \mathbb N$ and suppose it is known that every factor of $n$ is of the form $ax+b$ for some (known) integers $a,b$, then from $n = (ax_1+b)(ax_2+b)$ he saw that there existed $q,h,r$ integers such that : $$ x_1x_2 = q-bh \\ x_1+x_2 = r+ah\\ h = \frac{q-x_1(r-x_1)}{ax_1+b} $$
using which he was able to test for existence of $q,h,r$ for various values of $x_1$. He proved the existence of a $B>0$, such that it is enough to have no solutions to the first two equations for $x_1 > B$ and no solution to the third equation for $x_1 \leq B$ for $n$ to be prime. If there is a solution at some stage, then $n$ is not prime!
Landry used this to factorize $2^n \pm 1$ for all $n \leq 64$ completely (with the apparent exception of four of them near $64$), and also obtained the largest prime number known then : $$ \frac{2^{53}+1}{321} = 2805980762433 $$
They do work very very hard in computation, though. Lucas confirmed that $M_{67}$ was composite, but no prime factor was found till $1903$ when Frank Nelson Cole took , after "three years of Sundays", to the blackboard in a famous "no speech" seminar , proceeded to square $2$ repeatedly and find $$ 2^{67}-1 = 147573952589676412927 $$
and on the other side of the board, proceeded to multiply : $$ \quad \quad \ \ \ \quad \quad \quad 193707721 \\ \quad \quad \quad\times 761838257287 \\ -----------\\ 147573952589676412927 \\ ----------- $$
in high school fashion. He said nothing , and cue rapturous applause. And why not!