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

Re: Lucas super-pseudoprimes for Q <> 1

Expand Messages
  • mikeoakes2
    Back in May, in http://tech.groups.yahoo.com/group/primenumbers/message/21508 ... (David gave a nice example of a large n where condition (c) meant that Q was
    Message 1 of 46 , Oct 30, 2010
    View Source
    • 0 Attachment
      Back in May, in
      http://tech.groups.yahoo.com/group/primenumbers/message/21508
      I wrote:
      >
      > Notation:
      > For integers P and Q, and nonnegative integer n, define V(P,Q,n) by the recurrence relation
      > V(P,Q,n) = P*V(P,Q,n-1)-Q*V(P,Q,n-2)
      > with initial conditions V(P,Q,0)=2, V(P,Q,1)=P.
      > Then as is well known V(P,Q,n)=x1^n+x2^n,
      > where x1, x2 are the roots of the quadratic equation x^2-P*x+Q=0.
      >
      > Conjecture:
      > If n is an odd composite integer, and V(P,Q,n) = P mod n for all P, for fixed Q>1, then
      > (a) n is not a multiple of 3;
      > (b) n is a Carmichael number, i.e. for all prime factors p of n, (p-1) divides (n-1);
      > (c) Q is a multiple of every prime factor p of n such that (p+1) does not divide (n^2-1).
      > Conversely, if (a) and (b) hold, and if we define Q_0 = product of every prime factor p of n such that (p+1) does not divide (n^2-1), then there is at least one Q which is a multiple of Q_0 and is such that V(P,Q,n) = P mod n for all P.
      >

      (David gave a nice example of a large n where condition (c) meant that Q was a multiple of 1.)

      I have just finished a 1 GHz-yr investigation of this Conjecture, and have to report that it is (very slightly:-) false.

      For every odd composite integer n < 10^6, not a multiple of 3, I found all Q < 10^6 satisfying the conditions of the Conjecture.

      In every case but one, n was indeed a Carmichael number, but for n = 507529 = 11*29*37*43, the conditions are satisifed, for Q a multiple of 1247 = 29*43, yet n is not a Carmichael number, as (11-1) does not divide (n-1).

      Is this surprising at all, David? (I've rather lost track of the theory after all this time).

      Mike
    • djbroadhurst
      ... http://physics.open.ac.uk/~dbroadhu/cert/dbmo116.out gives my 116, in the format [n, factors, number of solutions] With n
      Message 46 of 46 , Nov 9, 2010
      View Source
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "mikeoakes2" <mikeoakes2@...> wrote:

        > > My revised count up to 2*10^10 is 116.
        > My (original) count up to 2*10^10 was 105.
        > So it must have missed 11, i.e. a bigger proportion.

        http://physics.open.ac.uk/~dbroadhu/cert/dbmo116.out
        gives my 116, in the format [n, factors, number of solutions]

        With n < 2*10^10, the record-holder for the number of solutions is
        [2214495361, [13, 17, 23, 29, 83, 181], 147407]
        which googles quite nicely, linking to
        http://www.cs.rit.edu/usr/local/pub/pga/fibonacci_pp

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.