Find all integers n such that 2n − 1 is divisible by n.
Clearly we must have n 0. In fact, n = 0 and n = 1 are solutions. Now consider n > 1, where we will argue reductio ad absurdum.
Suppose n divides 2n − 1. Since n > 1, we can consider p, the smallest prime factor of n.
Note that 2n − 1 is odd, so n is odd, and p is odd. Hence p > 2.
Since p is the smallest prime factor of n, the greatest common divisor of n and p − 1 is 1.
Hence, by a standard corollary to Euclid's algorithm, there exist integers x and y such that nx + (p − 1)y = 1.
We may therefore write:
2 = 21 = 2nx + (p−1)y = 2nx × 2(p−1)y = (2n)x × (2p−1)y.
Now consider this equation, modulo p.
We have 2n 1 (mod 2n − 1), and so 2n 1 (mod n), and 2n 1 (mod p).
Also, by Fermat's Little Theorem, since the greatest common divisor of 2 and p is 1, we have 2p−1 1 (mod p).
Putting these two results together, we get 2 1x × 1y 1 (mod p); a contradiction. (Note that this is true even though one of x and y must be negative.)
Hence our original supposition, that there is a p which is the smallest prime factor of n, which divides 2n − 1, is false.
Therefore the only integers n such that 2n − 1 is divisible by n, are 0 and 1.
We may similarly show that, if p is prime, each prime divisor of 2p − 1 is greater than p. A corollary is that the number of primes is infinite!
The only known solutions of 2n 3 (mod n) are 4700063497, 8365386194032363, and 63130707451134435989380140059866138830623361447484274774099906755. See Sloane's A050259. Search for 4700063497 for further references.
Source: Putnam Sample Problems, number 7 (problem page since taken down)