Eric Hughes:

It was first claimed that if (2^n-2)/n was an integer, then n was prime. That's false.

I thought he said "if p prime, then p|(2^p-2)" which is why I stated the converse isn't true.

then:

...

This is fermat's little theorem. What you have written basically says 2^N - 2 = 0 (mod N) or 2^(N-1) = 1 (mod N). Note, the converse doesn't apply. If (2^N-2)/N is an integer, N isn't neccessarily prime. For example, take N=561=(3*11*37)

561 is the first Carmichael number. If you replace 2 by any other number relatively prime to 561, then the congruence still holds. (The second Carmichael number is 1729, if I remember right.) It was

Which is why I chose it. Carmichael numbers are pseudoprime in any valid base so when coming up with a counterexample to the converse of fermat's little theorem, just memorize a few Carmichael numbers. The key property of them is if n is a Carmichael number and n=p*q*r, then (p-1), (q-1), and (r-1) divide (n-1). I wonder if Carmichael numbers always have some small factors. If true, PGP's sieve test probably eliminates the very very rare case that you actually choose one. -Ray -- Ray Cromwell | Engineering is the implementation of science; -- -- rjc@gnu.ai.mit.edu | politics is the implementation of faith. --