Can you make mew understand the LLR Test?

[a1call]

Hi,
I am not too lazy to Google for a proof.
I am however too busy to decipher it to see why it works.
I figure if anyone can put it in layman's terms that I could comprehend, then she/he is got to be a member here.
Any insights as to why the LLR Test works would be greatly appreciated.

Thanks in advance.

ETA the swipes keyboard topped "new" instead of "me" in the title.

[henryzz]

I would try to understand the LL test first.

[paulunderwood]

http://primes.utm.edu/prove/index.html is a good starting point

[science_man_88]

Originally Posted by a1call

Hi,
I am not too lazy to Google for a proof.
I am however too busy to decipher it to see why it works.
I figure if anyone can put it in layman's terms that I could comprehend, then she/he is got to be a member here.
Any insights as to why the LLR Test works would be greatly appreciated.

Thanks in advance.

ETA the swipes keyboard topped "new" instead of "me" in the title.

it's not that people here couldn't most likely but without a basic understanding of the context involved the wording would have to get almost arbitrarily large.

for example the wikipedia talks about groups do you know what these are if not they are a set along with a binary relation, satisfying specific axioms. what's a binary relation you ask well it's a operation between two things. what are axioms ? and which of them does it have to fit ? and wikipedia on how it works talks about orders of a group what is the order of a group ? without knowing the how it's potentially impossible to have a good grasp on the why.

[LaurV]

Originally Posted by henryzz

I would try to understand the LL test first.

Yes. And reading about Lucas Sequences and divisibility sequences in general, may help.

[Nick]

Another good reference is Bas Jansen's PhD thesis:
http://www.math.leidenuniv.nl/scripties/PhDJansen.pdf

Note: it begins with a summary in Dutch, but the main body of the document is in English.

[a1call]

Thank you very much for all the expert and undoubtedly excellent insights and links.
I will be working straight through the weekend, but I am watching this thread.
Others with the same question and phrasing will end up here as well by googling, so thanks to all.

[Raman]

Originally Posted by a1call

Hi,
I am not too lazy to Google for a proof.
I am however too busy to decipher it to see why it works.
I figure if anyone can put it in layman's terms that I could comprehend, then she/he is got to be a member here.
Any insights as to why the LLR Test works would be greatly appreciated.

Thanks in advance.

ETA the swipes keyboard topped "new" instead of "me" in the title.

"Lucasian Criteria for the Primality of N = h.2ⁿ-1" by Hans Riesel

Originally Posted by Raman

LUCAS LEHMER RIESEL TEST

The Lucas Lehmer Test can be extended further to prove that numbers of the form
p = h.2ⁿ-1 are prime, where h < 2ⁿ. It depends upon choosing a clever value for S₁.

If h = 1, then S₁ = 4 will hold for all odd values of n, and S₁ = 3 will hold for all n ≡ 3 (mod 4)

If h = 3, then S₁ = 5778 can be used for all n ≡ 0, 3 (mod 4)

If h = 6k ± 1, k is an integer, then S₁ = (2 + √3)^h + (2 - √3)^h can be used for all the values

of n. Note that, here we use the value of P = 4 and Q = 1 and calculate the value of V_h.

Otherwise, we are left with the case where h is a multiple of 3, and we have to be more

careful in choosing the value of S₁.

Try with v₁ values starting from 3, and let D be the square free part of v₁² - 4.

Let v₁ = α + α^-1, and so v₁ satisfies the equation α² - v₁α + 1 = 0.

Now, that the values of a and r are obtained from the following equations:

a = (a + b√D)²/r and r = |a² - b²D|, b = 1 .

Let k = √[(v₁² - 4)/D]. Then, α = [v₁ + √(v₁² - 4)]/2 = [v₁ + k√D]/2.

This corresponds to [(a² + b²D) + 2ab√D]/r. So, that now we can now easily solve for a

and r. These should satisfy the following equations:

(D/N) = -1, (r/N)(a² - b²D)/r = -1. If not choose a different value for v₁.

Then, the starting value S₁ is taken to be α^h + α^-h, that is V_h with P = V₁ and Q = 1,
satisfying the Lucas equation x² - Px + Q = 0. The value of V_h can be calculated by using
the following recurrence equations.
V₀ = 2, V₁ = P, V_n = PV_n-1 - QV_n-2 for all n ≥ 2. V_2n = V_n² - 2Qⁿ, V_2n-1 = V_nV_n-1 - PQ^n-1.

[a1call]

"Can you make mew"
Very funny Batalov.
That actually put a smile on my face after a long day.

[Batalov]

I guess my swipes keyboard topps oneders, two!