Sorry, an error occurred while loading the content.

## Re: Lucas super-pseudoprimes for Q <> 1

Expand Messages
• ... 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
• ... 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.