We apply Fermat’s method of infinite descent to the prime factors of n . Let p1 be prime divisor of n and q be the smallest positive integer for which p1 divides 2q-1. From Fermat’s Little theorem it follows that p1 divides 2p1-1-1. Also we have q< p1-1<p
Let us prove that q divides n. If not let n=kq+r, where 0<r<q. Then 2n-1=2kq2r-1=(2q-1+1)2r-1 which is obviously equal to 2r-1 modulo p1.
It follows that p1 divides 2r-1, contradicting the minimality of q. Hence q divides n and 2q<p1. Let p2 be a prime divisor of q. Then it is also a divisor of n and hence p2<p1. Repeating the argument we construct an infinite sequence of prime divisors.
Hence the proof follows.
This problem is from the 1st Putnam in 1939 most probably!
