The $\textbf{overall idea of this proof}$ is to start by assuming that $M_p$ divides $S_{p-1}$, and then consider that $M_p$ is not a prime which will lead us to a contradiction. If you want to learn more about the discovery of $M_{74,207,281}$ it's worth watching this video [](https://www.youtube.com/watch?v=lEvXcTYqtKU "How they found the World's Biggest Prime Number") $(2+\sqrt{3})(2-\sqrt{3})=2^2 - \sqrt{3}^2 = 4 - 3 = 1$ Yes, if $M_p$ doesn't divide $S_{p-1}$ it's not prime. Is the theorem if and only if? Note that $\bar w w = 1$ and so $w \in X^*$ In pseudocode, the test might be written as ``` // Determine if Mp = 2^p − 1 is prime Lucas–Lehmer(p) var s = 4 var M = 2p − 1 repeat p − 2 times: s = ((s × s) − 2) mod M if s == 0 return PRIME else return COMPOSITE ``` The Lucas-Lehmer test reduces substantially the complexity to prove the primality of the number - O($p^2\log p \log \log p$) To prove that this result is equivalent to $S_m = S^2_{m-1}-2$ we just need to calculate $S_{m-1}$ $$ S^2_{m-1}=(w^{2^{m-2}}+\bar w^{2^{m-2}})^2=w^{2^{m-1}}+\bar w^{2^{m-1}}+2(w\bar w)^{2^{m-2}}=\\ =w^{2^{m-1}}+\bar w^{2^{m-1}}+2=S_m+2 $$ Note that $Z_q$ has $q$ elements: {$\bar 0, \bar 1, \bar 2, ..., \overline {q-1}$} and so $X$ has $q\times q = q^2$ elements as we have $q$ options for $a$ and another $q$ options for $b$. In case of $X^*$ since 0 is non-invertible we have $q^2-1$ elements. Does the . operator here represents a binary operation or the multiplication operation ? A basic theorem about Mersenne numbers states that if $M_p$ is prime, then the exponent $p$ must also be prime. To prove this let's assume that $p$ is composite $p=ab$. In that case it's possible to write $$ M_p= 2^{ab}-1=(2^{a}-1)(1+2^a+2^{2a}+...+2^{(b-1)a}) $$ which means that $M_p$ is divisible by $2^a-1$ and thus not prime! Does the . operator here represents a binary operation or the multiplication operation ? The order of a group is the number of elements in that group and the order of an element $a$ is the smallest positive integer $m$ such that $a^m = 1$. To prove Lemma 3 let's consider a group that has 3 elements a,b and 1. If $a \neq aa \neq aaa \neq aaaa $ we have already 4 different elements in the group which is a contradiction since the order of the group is 3. Thus the order of $a\leq3$. For $X^*$ to form a group we just need to prove the Closure property: For all $x_1^-1$, $x_2^-1$ in $X^*$, the result of the operation, $x_1^-1.x_2^-1$, is also in $X^*$. We know that $x_1.x_1^-1=1$ and $x_2.x_2^-1=1$ but we need to prove that $x_1.x_2$ has an inverse. Now, if we calculate $$ x_1.x_2.x_2^{-1}.x_1^{-1}=x_1.1.x_1^{-1}=x_1.x_1^{-1}=1 $$ and so $x_2^{-1}.x_1^{-1}$ is the inverse of $x_1.x_2$. Don't forget that we chose $q$ above as a prime divisor of $M_p$ and so $M_p \equiv 0$ modulo $q$, which means that $RM_pw^{2^{p-2}} \equiv 0$ modulo $q$. If you want to read Rosen's original paper click [here](http://fermatslibrary.com/s/a-proof-of-the-lucas-lehmer-test) Let $|\omega|$ denote the order of $\omega$. If $|\omega| < 2^p$ and divides $2^p$, $|\omega|$ must divide $2^{p-1}$, since the only prime factor of $2^p$ is $2$. It is curious to notice that for any real number a and integer n the relation $ (a^{n} - 1) $ can be rewritten as: $$ (a^{n} - 1) = (a-1)\cdot P(a) $$ where P(a) is a polynomial. One can prove this by induction. For 1 it is trivial. Let's consider two scenarios where n is even and n is odd. For n = 2 (even): $$ (a^{2} - 1) = (a-1)(a+1) $$ For n = 3 (odd): \begin{eqnarray*} (a^{3} - 1) &=& a^{3} - 1 + a^{2} - a^{2}\\ &=& (a^{2} - 1) + a^{3} - a^{2} \\ &=& (a - 1)(a^{2} + a + 1) \end{eqnarray*} One can then write that for any integer k: \begin{eqnarray*} (a^{n} - 1) &=& (a - 1)\sum_{n=0}^{n-1} a^{k} \end{eqnarray*} Hi, I am not getting how the order of $\omega$ is $2^p$. In the second equality, we have $w^{2^{p}}=1$, that means order of $\omega$ divides $2^p$. But how $w^{2^{p-1}}=-1$ ensures that there is no smaller power of $\omega$ which equals $1$? The Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1856 and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s. Mersenne numbers can be written in the form $$ M_n = 2^n-1 $$ where $n$ is an integer. Mersenne numbers are named after the French monk Marin Mersenne (1588–1648) who compiled a list of Mersenne primes. These numbers have very interesting properties, in particular there are conjectures that predict there are an infinite number of Mersenne primes, but these have not been settled. The largest known prime number is a Mersenne prime $M_{74,207,281}$, proved prime in 2015. One reason for the prevalence of Mersenne primes in the record books is because the Lucas-Lehmer test is a relatively easy test from a computational standpoint for the primality of a Mersenne number. In fact, since $M_{521}$ was proven prime in 1952, the largest known prime has always been a Mersenne prime (with one exception in 1989). See a [history of prime number records](http://primes.utm.edu/notes/by_year.html). The Lucas–Lehmer test is the primality test used by the [Great Internet Mersenne Prime Search](https://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search) to locate large primes. This search has been successful in locating many of the largest primes known to date. The set of all integers which have the same remainder when divided by $q$ is called the $\textbf{congruence class}$ of a modulo $q$. The collection of all congruence classes modulo q is called the $\textbf{set of integers modulo q}$, denoted by $Z_q$ For instance, the set of integers modulo 3 $Z_3$ has three elements which we will call {$\bar0,\bar1,\bar2$}. Don't confuse these elements with the regular integers 0,1,2. As an example, $\bar 2$ denotes the set of all integers which have remainder 2 when divided by 3 {2,5,8,...} Now we can perform standard modular arithmetic to determine the addition and multiplication tables for this set. We find that $\bar 1.\bar 1= \bar 1 $, and $\bar 2.\bar 2= \bar 4= \bar 1$. Thus, both of the nonzero elements have inverses! Note that in computing the multiplication I mentioned a new element $\bar 4$ that looks out of place. But it's okay, because we know that $\bar 4 \equiv \bar 1$ mod 3. So we can always do normal arithmetic under the bar and then simplify it afterward. This is why modular arithmetic is so easy! We see that this can happen in a finite field because there isn't room for numbers to keep getting bigger and bigger. Instead, multiplication "wraps around" until it gets to $\bar1$ and you find your inverse. This trick only works because $q$ was prime. If $q$ was not prime we could write $q=ab$ as a product of 2 primes. Then, we would not be able to find an inverse for $a$, because in the integers modulo $q$, we have that $\bar a \bar b=\overline{ab} =\bar 0$. So if there were some $\bar c$ such that $\bar a\bar c=1$, then we would have $\bar b = \bar a \bar c \bar b=\bar 0$, a contradiction!