Talk:Lucas–Lehmer test for Mersenne numbers

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

B Class

Low Priority

Field: Number theory

Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

there is a mistake in the article , it supposed to :
$s_{p-1}\equiv0\pmod{M_p};$
not :
$s_{p-2}\equiv0\pmod{M_p};$

—The preceding unsigned comment was added by 85.250.124.207 (talk • contribs) 07:26, 4 November 2005 (UTC).

I disagree.

M 3

is prime and also $s_1\equiv0\pmod{M_3}$ . That is, $14\equiv0\pmod7$ . However, $s_2\ \not\equiv\ 0\pmod{M_3}$ ; equivalently, $194\ \not\equiv\ 0\pmod7$ . Therefore I think the article is correct as is stands. Eric119 03:35, 5 November 2005 (UTC)

$s 0 = 4$ , so is $s_{p-2}\equiv0\pmod{M_p}$ and not $s_{p-1}\equiv0\pmod{M_p}$ .

[edit] Dumbing this down with an example?

I think it might help some people by giving an example of how the Lucas-Lehmer test can prove primality of say... 2^5-1, for instance. As the article stands, not many people without prior experience of advanced mathematical notation and terms, would be able to take anything useful from this.

Great idea. Dcoetzee 03:24, 10 May 2007 (UTC)

[edit] A bit confused about high speed mod

I'm a bit confused about the high speed mod operation. The article gives this example:

916 mod 2⁵−1 = 1110010100 mod 2⁵−1

= 11100 + 10100 mod 2⁵−1 
= 110000 mod 2⁵−1 
= 1 + 10000 mod 2⁵−1 
= 10001 mod 2⁵−1 
= 10001 
= 17.

However if I try it with 14 mod 7 I get this: 14 mod 2³−1

= 1110 mod 2³−1 
= 1 + 110 mod 2³−1 
= 111 mod 2³−1 
= 7.

Now I know that 7 mod 7 is 0, but how does the ggiven algo generate a zero ? Thanks —Preceding unsigned comment added by 149.173.6.50 (talk) 15:25, 20 November 2007 (UTC)

That's a good observation, actually - it's possible for the result to be exactly 2ⁿ−1, in which case you have to change it to zero. If it were any larger, you'd reduce it by doing another iteration. Dcoetzee 01:23, 21 November 2007 (UTC)

I think, there are little problems whit this reasoning. First of all, if the modulo operation gives us 0 as a result, then this leads to the next: We arrive at 0, then we square it, it becomes 0 again, then we substract 2, then it is -2. Now, due to the [[1]] article, we can define the modulo of -2, so:

-2 = M_p-2 (mod M_p)

but this computation, namely, that we add M_p to the resutl to get a positive integer is much different from the algorithm described in this article.

Morover, this article states:

"since s × s will never exceed M² < 2^2p"

This statement eables, that the value after the squaring operation be M2^2p, and thus, the value before the squaring operation be M². So if the resutlt after the modulo operation is M_p, then we dont't need to convert it to 0.

So it would be needed to clarify this article on my opinion.