## The Lucas-Lehmer Theorem

The largest prime was discovered eighteen days ago by a mathematician named Curtis Cooper. The specific prime that he found was a Mersenne prime $2^{74207281}-1$ which contains exactly $22338618$ digits. Although found by chance, there was some mathematics involved that computers used to determine if a certain number was prime or not.

It is called the Lucas-Lehmer “Theorem” (better off as a “sequence”) in which we start from the number $4$ with the next number being $n^2-2$. So the sequence would go $\{4, 14, 194, 37634,\cdots\}$ and it will continue to rapidly increase exponentially.

Let us consider the example $2^3-1=7$ which is indeed prime. To verify, we take the exponent, $3$, and subtract $1$ to get $2$ ($3-1=2$). We then take a look at the second term in the Lucas-Lehmer “sequence” which is $14$. We need to show that $14$ is divided with remainder $0$ by the “prime” number $7$. So

$14 \ \text{mod} \ 7=0.$

And indeed we receive a remainder of $0$ therefore confirming that $7$ is prime.

So let $a=2^n-1$ such that $n\in J$ and the Lucas-Lehmer “sequence” be denoted by $\{b_{n-1}\}_{n\in J}$. Then for a given “testable” number, it is prime iff

$(b_{n-1}) \ \text{mod} \ (a)=0.$

Otherwise, not prime.

Today’s post is short because I have finals this week. More to come next week!