Loading ...
Sorry, an error occurred while loading the content.
 

Yet another Lucas-Lehmer like primality test ?

Expand Messages
  • j_chrtn
    Hello, I recently found the following statements : Let L(k) be the Lucas sequence L(0)=2, L(1)=1, L(k+2) = L(k+1) + L(k) Let M(n, p) = (n+1)^p - n^p for n = 1
    Message 1 of 3 , May 5, 2007
      Hello,

      I recently found the following statements :

      Let L(k) be the Lucas sequence L(0)=2, L(1)=1, L(k+2) = L(k+1) + L(k)

      Let M(n, p) = (n+1)^p - n^p for n >= 1 and p prime >= 3 (M(n,p) can
      be viewed as a generalization of Mersenne's number).

      1/ Let n >= 1 such that n mod 5 is 0, 2 or 4
      Then :

      M(n, p) is prime if and only if M(n, p) divides L((n+1)^p) - L(n^p
      + 1)


      2/ Let n >= 1 such that n mod 5 is 1 or 3 and let p prime >= 3 such
      that p mod 4 is 1
      Then :

      M(n, p) is prime if and only if M(n, p) divides L((n+1)^p) - L(n^p
      + 1)


      It follows an efficient primality test for M(n, p) just like the well
      known Lucas-Lehmer test for Mersenne's numbers.

      I would like your feedback on this. Is it a known result ?

      Best regards,

      J-L Charton.
    • Phil Carmody
      ... Welcome to the list. ... Yes, one that s been used by several before you. ... I m not familiar with it. I suspect that it s not a proven result as a
      Message 2 of 3 , May 5, 2007
        --- j_chrtn <j_chrtn@...> wrote:
        > Hello,

        Welcome to the list.

        > I recently found the following statements :
        >
        > Let L(k) be the Lucas sequence L(0)=2, L(1)=1, L(k+2) = L(k+1) + L(k)
        >
        > Let M(n, p) = (n+1)^p - n^p for n >= 1 and p prime >= 3 (M(n,p) can
        > be viewed as a generalization of Mersenne's number).

        Yes, one that's been used by several before you.

        > 1/ Let n >= 1 such that n mod 5 is 0, 2 or 4
        > Then :
        >
        > M(n, p) is prime if and only if M(n, p) divides L((n+1)^p) - L(n^p
        > + 1)
        >
        >
        > 2/ Let n >= 1 such that n mod 5 is 1 or 3 and let p prime >= 3 such
        > that p mod 4 is 1
        > Then :
        >
        > M(n, p) is prime if and only if M(n, p) divides L((n+1)^p) - L(n^p
        > + 1)
        >
        >
        > It follows an efficient primality test for M(n, p) just like the well
        > known Lucas-Lehmer test for Mersenne's numbers.
        >
        > I would like your feedback on this. Is it a known result ?

        I'm not familiar with it. I suspect that it's not a proven result as a
        primality test. It might well be a compositeness test (Probable Primality
        test). The way primiality proofs almost always work is that they limit the
        size and form of divisors of the number in question (e.g. if you prove they're
        all greater than the square root of the number, then you're sorted). I don't
        see how satisfying your criterion alone says anything about the size of
        divisors.

        Aside - who is recording these primes, I don't think it's one of Jens' or
        Steven's forms, is it?

        Phil

        () ASCII ribbon campaign () Hopeless ribbon campaign
        /\ against HTML mail /\ against gratuitous bloodshed

        [stolen with permission from Daniel B. Cristofani]

        __________________________________________________
        Do You Yahoo!?
        Tired of spam? Yahoo! Mail has the best spam protection around
        http://mail.yahoo.com
      • j_chrtn
        Hi Phil, ... (k) ... can ... (n^p ... such ... (n^p ... well ... as a ... Primality ... limit the ... prove they re ... sorted). I don t ... size of ... Well,
        Message 3 of 3 , May 5, 2007
          Hi Phil,

          --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@...>
          wrote:
          >
          > --- j_chrtn <j_chrtn@...> wrote:
          > > Hello,
          >
          > Welcome to the list.
          >
          > > I recently found the following statements :
          > >
          > > Let L(k) be the Lucas sequence L(0)=2, L(1)=1, L(k+2) = L(k+1) + L
          (k)
          > >
          > > Let M(n, p) = (n+1)^p - n^p for n >= 1 and p prime >= 3 (M(n,p)
          can
          > > be viewed as a generalization of Mersenne's number).
          >
          > Yes, one that's been used by several before you.
          >
          > > 1/ Let n >= 1 such that n mod 5 is 0, 2 or 4
          > > Then :
          > >
          > > M(n, p) is prime if and only if M(n, p) divides L((n+1)^p) - L
          (n^p
          > > + 1)
          > >
          > >
          > > 2/ Let n >= 1 such that n mod 5 is 1 or 3 and let p prime >= 3
          such
          > > that p mod 4 is 1
          > > Then :
          > >
          > > M(n, p) is prime if and only if M(n, p) divides L((n+1)^p) - L
          (n^p
          > > + 1)
          > >
          > >
          > > It follows an efficient primality test for M(n, p) just like the
          well
          > > known Lucas-Lehmer test for Mersenne's numbers.
          > >
          > > I would like your feedback on this. Is it a known result ?
          >
          > I'm not familiar with it. I suspect that it's not a proven result
          as a
          > primality test. It might well be a compositeness test (Probable
          Primality
          > test). The way primiality proofs almost always work is that they
          limit the
          > size and form of divisors of the number in question (e.g. if you
          prove they're
          > all greater than the square root of the number, then you're
          sorted). I don't
          > see how satisfying your criterion alone says anything about the
          size of
          > divisors.

          Well, you're right: at this time, I have unfortunately not been able
          to prove these assertions. However, as far as I know Lucas-Lehmer
          test is based on the rank of apparition of a given prime P in the
          Fibonacci or Lehmer extension sequences and the relationships between
          these sequences and their companion Lucas or Lehmer extension
          sequences. I suspect that my two statements above may be proved the
          same way ...


          >
          > Aside - who is recording these primes, I don't think it's one of
          Jens' or
          > Steven's forms, is it?

          I don't know if someone officially records this form of primes. I
          just know that we (Mike Oakes, Predrag Minovic, myself and maybe
          other people) have recorded many PRP of this form to Henri Lifchitz
          probable primes page.

          The largest known PRP of this form (which is my current record) is
          10^282493-9^282493.

          J-L.
        Your message has been successfully submitted and would be delivered to recipients shortly.