Find all integers n such that 2^{n} − 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 2^{n} − 1. Since n > 1, we can consider p, the smallest prime factor of n.

Note that 2^{n} − 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 = 2^{1} = 2^{nx + (p−1)y} = 2^{nx} × 2^{(p−1)y} = (2^{n})^{x} × (2^{p−1})^{y}.

Now consider this equation, modulo p.

We have 2^{n} 1 (mod 2^{n} − 1), and so 2^{n} 1 (mod n), and 2^{n} 1 (mod p).

Also, by Fermat's Little Theorem, since the greatest common divisor of 2 and p is 1, we have 2^{p−1} 1 (mod p).

Putting these two results together, we get 2 1^{x} × 1^{y} 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 2^{n} − 1, is false.

Therefore the only integers n such that 2^{n} − 1 is divisible by n, are 0 and 1.

We may similarly show that, if p is prime, each prime divisor of 2^{p} − 1 is greater than p. A corollary is that the number of primes is infinite!

2^{n} 2 (mod n) whenever n is prime (by Fermat's Little Theorem) or is a pseudoprime base 2. The first few pseudoprimes base 2 are 341, 561, 645, 1105, 1387, 1729, 1905, ... (Sloane's A001567.)

The only known solutions of 2^{n} 3 (mod n) are 4700063497, 8365386194032363, and 63130707451134435989380140059866138830623361447484274774099906755. See Sloane's A050259. Search for 4700063497 for further references.

The Lehmers found solutions of 2^{n} k (mod n) for all k such that |k| < 100, except for k = 1. See Sloane's A036236 and A036237.

Source: Putnam Sample Problems, number 7 (problem page since taken down)