A question was asked on Mersenneforum.org about why the Lucas-Lehmer test works. The answer given was basically "You need to study Number Theory for years and years to understand the complexity behind why the test works".
Okay, so that's my tongue-in-cheek summarization, but the thread did get a little heated.
I've done a little work with the Lucas-Lehmer sequence, and have found some surprising relationships to Quadratic Residues. Of course, without the years and years of Number Theory studies, I can't come up with a proof, so I'll never get my name on it. ;-)
Basically, it comes down to the fact that all terms of the Lucas-Lehmer sequence modulo a Mersenne number (Mp = 2^p - 1) must be a quadratic residue of that Mersenne number for it to be a Mersenne Prime. If you hit a term in the LL sequence that is not a QR of Mp, then Mp is composite.
Note: I'll qualify by saying that you need to verify that +/- the LL term must be a QR, because of one of those weird Number Theory things. For example, term 2 of the LL modulo 127 is 67. However, 67 is not a QR of 127. But, 127 - 67 = 60, which is a QR, so the test still passes.
So, here appears to be a necessary condition for primality. But that still does not answer the question of "why".
Well, this is where Number Fields come in handy. I'm no expert on fields, but you don't need to be in order to see how a field behaves.
Quadratic residues of a Mersenne Prime form a field of numbers with exactly (2^(p-1) - 1) elements. Each of these elements, when squared (mod Mp) results in another number in the field. This leads to a beautiful cyclical sub-field of exactly p-1 elements (meaning that the subfield starts to repeat itself every p element).
Here is an example of that sub-field effect starting with 44 modulo 127:
44 31 72 104 21 60 44
31 = 44^2 mod 127; 72 = 31^2 mod 127; etc
This behavior does not always exist with composite numbers, because the prime factors of those numbers somehow interfere with the field's behavior (during the modulo operation, I would guess). You end up with something like the fields for each prime factor overlapping, which distorts the results.
For example, here's two subfields modulo 2047 (a Mersenne composite = 23*89). Each starting number is a QR of 2047, but :
64 2 4 16 256 32 1024 512 128 8 64
36 1296 1076 1221 625 1695 1084 78 1990 1202 1669
Notice that 64's subfield correctly "wraps around" after 11 iterations, but 36 fails to. This shows that some subfields are cyclical, while others aren't (because of that interference effect).
When we continue squaring the subfield modulo 2047, we see that we actually jump into another cyclical subfield of the proper length:
36 1296 1076 1221 625 1695 1084 78 1990 1202 1669 1641 1076
In this case, both 1296 and 1641 are modular square roots of 1076, but the subfield containing 1296 actually turns into the subfield containing 1641. The fact that there are two roots for a QR is not unusual, but these numbers are not +/- the same number, as the roots of a prime's QR would be. The overall result is that the field containing all QR's of a Mersenne composite turns out to contain less than 2^(p-1) - 1 elements. (In this example, think because 36 did not have it's own 11 numbers, it only added 2 numbers to the total field).
So, the LL sequence is related to the same mechanism that causes the beautiful cyclical patterns of the quadratic residue subfields. These patterns only exist modulo prime numbers. Composite numbers cause one subfield to change into another. This same mechanism leads to the LL sequence to fail for composite numbers.
And, of course, I don't have any further explaination for this phenomenon, so you'll need to study Number Theory for a while. ;-)
For reference, here is a breakout for M7 (127 = 2^7 - 1). The field of QR's shown are x^2 % Mp, and are Quadratic Residues because they have modulo square roots (x).
Mp LL -LL x QR x QR
127 4 123 1 1 33 73
14 113 2 4 34 13
67 60 3 9 35 82
42 85 4 16 36 26
111 16 5 25 37 99
--> 0 127 6 36 38 47
125 2 7 49 39 124
2 125 8 64 40 76
2 125 9 81 41 30
2 125 10 100 42 113
2 125 11 121 43 71
2 125 12 17 44 31
2 125 13 42 45 120
2 125 14 69 46 84
2 125 15 98 47 50
16 2 48 18
17 35 49 115
18 70 50 87
19 107 51 61
20 19 52 37
21 60 53 15
22 103 54 122
23 21 55 104
24 68 56 88
25 117 57 74
26 41 58 62
27 94 59 52
28 22 60 44
29 79 61 38
30 11 62 34
31 72 63 32
32 8
