# Solution to puzzle 83: Divisibility

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.

## Remarks

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!

2n 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 2n 3 (mod n) are 4700063497, 8365386194032363, and 63130707451134435989380140059866138830623361447484274774099906755.  See Sloane's A050259.  Search for 4700063497 for further references.

The Lehmers found solutions of 2n 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)

Back to top