Show that n does not divide 2n - 1 for n > 1.
Solution
Suppose that n does divide 2n - 1. Then n must be odd. Let p be the smallest prime dividing n. Then 2p-1 = 1 (mod p). Let m be the smallest divisor of p - 1 such that 2m = 1 (mod p). Since m is smaller than p it must be coprime to n, so n = qm + r with 0 < r < m. Hence 2r = 1 (mod p). Contradiction.
© John Scholes
jscholes@kalva.demon.co.uk
27 Jan 2001