Results 1 to 4 of 4

Math Help - Lucas-Lehmer test (proof)

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    Lucas-Lehmer test (proof)

    Recall the Lucas Lehmer primality test for Mersenne primes which claims the following:

    2^p - 1 is prime iff s_{p-1} \equiv 0 mod{p}

    where s_1 = 4 and s_i \equiv s_{i-1}^2 - 2 mod{p}.

    Does anyone know the details to the proof of this important theorem? I've been trying to work it out on my own, but its tough.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148
    The proof on wiki was much easier to follow than many others I've seen, thanks. Who would have though that one could consider the orders of elements in the integral domain Z_p + Z_p \cdot \sqrt{3} in order to solve this!?

    Thanks again.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2008
    Posts
    148
    I'm finding that for prime Mersennes q = 2^p - 1, one doesn't necessarily need to have s_0 = 4 in order for s_{p-2} \equiv 0 mod(q).

    Consider the prime 2^7 - 1 for instance. If s_0 is in the following set we have that s_{p-2} \equiv 0 mod(q).

    {3,4,10,18,21,27,37,38,43,44,46,49,51,52,54,63,64, 73,75,76,78,81,83,84,89,90,100,106,109,117,123,124 }

    I'm guessing there is a probalistic reason for this occurence. Anyone wanna try to work through it with me?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Ironing out the Lucas Primality Test proof
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: April 24th 2010, 06:31 PM
  2. Proof about Fibonacci and Lucas numbers (GCD)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 21st 2010, 09:26 AM
  3. Subspace Test Proof (of test not subset)
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 15th 2010, 09:58 AM
  4. Lucas Numbers
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 4th 2009, 04:27 AM
  5. Lucas Number Proof By Induction
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 16th 2008, 04:08 PM

Search Tags


/mathhelpforum @mathhelpforum