Let M:=2^e-1, if M prime then phi(M)=2*(2^{e-1}-1) Now, observationally (tested all exponents e up to 5000 and some regions with e>5000): if ( 3^{2^{e-1}}==-3 mod M ) <==> M is prime Notation: [TS] <==> [P] The direction [P] ==> [TS] is easy excluding even exponents: 3 does not divide M and is a nonresidue. I cannot prove [TS] ==> [P]. I tried hard and failed with all ideas. Even additional assumptions (like that none of the 2^k powers of 3 in the test before the -3 equals minus -3) didn't lead to a proof. Before I waste time trying to prove something that is just false: Can ( [TS] ==> [P] ) be true? I'd be surprised to see a false hit or miss with the implied test but someone one this list may know better. I consider the test (if valid) a nice footnote because it consists of just squaring, no additions/subtractions. Further, a proof might give insight to primality tests for less restricted candidates. clueless, jj -- p=2^q-1 prime <== q>2, cosh(2^(q-2)*log(2+sqrt(3)))%p=0 Life is hard and then you die.