The above is obviously true for N=1.

If N is even, then the above is obviously false.  So consider odd N's.  ie, gcd(2, N)=1.

By fermat's last theorem, if N=p is prime, then 2^(p-1)=1(mod p) as gcd(2, p)=1.  So p divides 2^(p-1)-1, which implies p divides 2^p-2, meaning p cannot divide 2^p-1.

Now it remains to work out the part where N is not a prime and I need to think harder about this part.

Edited on December 12, 2004, 7:00 pm

Posted by Bon on 2004-12-12 18:40:03