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

Re: Lucas super-pseudoprimes for Q <> 1

Expand Messages
  • djbroadhurst
    ... Off list, Mike asked for a proof that this works, i.e. that there exists at least one integer Q with n Q 0 and V(P,Q,n) = P mod n, for every integer P,
    Message 1 of 46 , Nov 7, 2010
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "djbroadhurst" <d.broadhurst@...> wrote:

      > {ncarm(n)=local(F=factor(n),f=F[,1],m=#f,p,t,d);if(m>3&&
      > sum(j=1,m,F[j,2])==m,t=1;for(j=1,m,p=f[j];if((n-1)%(p-1),
      > if((n-1)%(p+1)==0&&(n+1)%(p-1)==0,d++,t=0;break()))));t&&d;}

      Off list, Mike asked for a proof that this works, i.e.
      that there exists at least one integer Q with n > Q > 0 and
      V(P,Q,n) = P mod n, for every integer P, whenever ncarm(n)
      returns 1.

      Proof: Consider any prime p|n. We have required that one of
      1) p-1|n-1 [Korselt]
      2) p+1|n-1 and p-1|n+1 [Pinch criterion "B^1"]
      holds. Moreover we have required that there is at least
      one prime where (1) does not hold and hence (2) must hold.
      Hence by the CRT there exists an integer Q with
      Q = 0 mod p in case (1) and Q = 1 mod p in case (2).
      In case (1), V(P,Q,n) = V(P,0,n) mod p = P^n mod p = P mod p.
      In case (2), V(P,Q,n) = V(P,1,n) mod p and we obtain P mod p
      when kronecker(P^2-4,p) = -1, since n = +1 mod p+1, and also
      when kronecker(P^2-4,p) > -1, since n = -1 mod p-1.
      Hence my code gives sufficient conditions for a solution, as claimed.

      NB: There may be many more Q's than those in my proof.
      In the case n = 7*47*89*241 = 7056721 there are precisely 75383.
      I did not yet prove that the test delivers all n's with at least
      one Q of type "Oakes", though that seems to be probable.

      David
    • 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
      • 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.