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!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s