## Re: [PrimeNumbers] Yet another Lucas-Lehmer like primality test ?

Expand Messages
• ... 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 1 of 3 , May 5, 2007
• 0 Attachment
--- 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
• 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 2 of 3 , May 5, 2007
• 0 Attachment
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
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.