guy'stheorem

Guy's Theorem

2^n <> 1 (mod n)

Proof:

Let p be the smallest prime factor of n.

If 2^m == 1 (mod p) then m and p-1 must have a common

factor >= 2. [Fermat's Little Theorem says 2^(p-1) == 1 (mod p), too].

But n and p-1 are coprime.

[proof due mainly to Haugland]