Mersenne Primes

Mersenne primes are of the form $2^p-1$. The known values of $p$ for Mersenne primes are $[2,$ $3,$ $5,$ $7,$ $13,$ $17,$ $19,$ $31,$ $61,$ $89,$ $107,$ $127,$ $521,$ $607,$ $1279,$ $2203,$ $2281,$ $3217,$ $4253,$ $4423,$ $9689,$ $9941,$ $11213,$ $19937,$ $21701,$ $23209,$ $44497,$ $86243,$ $110503,$ $132049,$ $216091,$ $756839,$ $859433,$ $1257787,$ $1398269,$ $2976221,$ $3021377,$ $6972593,$ $13466917,$ $20996011,$ $24036583,$ $25964951,$ $30402457,$ $32582657,$ $37156667,$ $42643801,$ $43112609,$ $57885161,$ $74207281,$ $77232917,$ $82589933]$. Hence the largest Mersenne prime has $24,862,048$ decimal digits. Think of a number that is the size of several phone books.

The exponent of a Mersenne prime has to be prime. If the exponent equalled the product of non-units $a$ and $b$, then $2^{a\times b}-1$ $=$ $(2^a-1)$ $\times$ $(2^{a\times (b-1)} + 2^{a\times (b-2)}+\ldots + 2^a + 1)$. The right-hand side of the latter expression has $b$ terms. So $2^{a\times b}-1$ must be composite.

Also all factors of $2^p-1$, where $p$ is prime, are of the form $2\times p\times A+1$ for some positive integer value $A$. For example $2^{11}-1$ $=$ $23\times 89$; and $23$ $=$ $2\times 11\times 1 + 1$ and $89$ $=$ $2\times 11\times 4 + 1$.

A Mersenne primes $M_p$ can be proven prime using the Lucas-Lehmer (LL) test as follows. Set $s=4$ and then iterate $p-2$ times $s^2-2 \pmod{M_p}\rightarrow s$. If and only if the result is $0$ then $M_p$ is prime. However, a modern technique is to compute a base-3 Fermat probable prime test with its built-in Gerbicz-error-correcting, which is useful for calculations that take a modern personal computer several days to compute, one of many participating computers running for The Great Internet Mersenne Prime Search's server.