--- 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