Assume there is such N satisfying 2^N=1 mod (N), where N is odd.

Let p be the smallest prime divisor of N.  Since N is odd, p must be odd as well (>2).  Since p-1 is even, and p is the smallest divisor of N, we have gcd(N, p-1)=1.  Thus by Euclid's algorithm, we have

xN+y(p-1)=1 for some integer x and y.

Also, 2^N=1(mod N) implies 2^N=1(mod p), because if N divides 2^N-1, then every prime divisors of N divides 2^N-1 also.  Therefore,

2=2^(1)=2^(xN+y(p-1)) = ((2^N)^x)*(2^(p-1)^y).  The second term = 1^y=1 mod p, by fermat's little theorem.  The first term = 1^x=1 mod p from the previous paragraph.  Therefore, we have

2=1*1(mod p) --> 2=1(mod p).  Since p>2, this is obviously a contradiction.  Therefore, our assumption about the existance of N>1 satisfying 2^N=1 mod p is invalid.  Thus the only possible N = 1.

Edited on December 12, 2004, 7:12 pm

Posted by Bon on 2004-12-12 18:58:59