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 :
- $n \equiv \pm 3 \pmod{10}$.
- $n | F_{n+1}$.
- $n \nmid F_m$ for all $1 \leq m \leq n$ which are divisors of $n+1$.
and similarly $n$ is a prime number if :
- $n \equiv \pm 1 \pmod{10}$.
- $n | F_{n-1}$.
- $n \nmid F_m$ for all $1 \leq m \leq n-2$ which are divisors of $n-1$.
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 :
If a prime $p$ divides $M_{31}$ then $p \equiv 1,63 \pmod{248}$.
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!
Best Answer
To the best of my knowledge, the best known test to determine whether a Mersenne number is prime is the Lucas-Lehmer test. If you already know that $p$ is an odd prime (it doesn't work for $M_2 = 3$), let
$U_0 = 4$, and $U_{n+1} \equiv U_n^2 - 2 \pmod {M_p}$.
Then $M_p$ is prime if and only if $U_{p-2} \equiv 0 \pmod {M_p}$.
Taking the modulus at each step, to check the primality of $M_p$, only $2\cdot p$-bit numbers are necessary, thus the proof (or disproof) is computationally feasible even for larger $p$.
The mathematics behind that are more involved than I am ready to explain here.
Regarding the edit - I presume the most important thing is the line with the "why?".
For the assumed prime $p$ dividing $M_{17}$, let $k$ be the order of 2 in $\mathbb{Z}_p^\ast$ (the group of units [non-zero elements] of $\mathbb{Z}_p$).
Then $p \mid 2^n - 1 \iff 2^n \equiv 1 \pmod p \iff k \mid n$. The last can be seen by writing $n = q\cdot k + r\quad, 0 \leqslant r < k$.
So by assumption $k \mid 17$, and by Fermat's theorem, $k \mid (p-1)$. Hence $k \mid (17, p-1)$.
That's not quite correct as stated, but assuming $M_{17}$ composite, and $p$ its smallest prime divisor, the conclusion $p \leqslant \sqrt{2^{17}-1}$ holds. (Since $M_p \equiv 3 \pmod 4$, we can replace the $\leqslant$ with a $<$.)