--- In firstname.lastname@example.org
"djbroadhurst" <d.broadhurst@...> wrote:
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)
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.