Puzzled: Uncommon Divisors

The theme is divisibility. A number n is said to divide a number m, written "n|m", if m is an integer multiple of n; for example, "m is even" is the same as saying 2 divides m.

1. Does every positive integer divide some number whose representation (base 10) contains only zeroes and ones? For example, if we start computing multiples of 7, we find that 1,001 = 7 x 143 is among them. Then again, maybe 7 is just a lucky number.

2. Does every positive integer divide some Fibonacci number? Recall that the Fibonacci numbers begin 1, 1, after which each is the sum of the previous two; 1, 1, 2, 3, 5, 8, 13, 21, 34…; for example, 7 works (again), since 7 x 3 = 21, or the eighth Fibonacci number.

3. A perfect number m is a positive integer that is the sum of its proper divisors; that is, the sum of all n less than m, such that n|m. The first perfect number is 6; 1, 2, and 3 are its proper positive divisors, and 1 + 2 + 3 = 6. The next perfect number is 28 = 1 + 2 + 4 + 7 + 14, and the next six are

496;

8128;

33,550,336;

8,589,869,056;

137,348,691,328; and

2,305,843,008,139,952,128.

The first four perfect numbers were known in ancient Greece; the eighth goes back to Swiss mathematician Leonhard Euler in 1772.

Note that all these numbers—in fact all 47 known perfect numbers—are even. The even perfect numbers are in a sense well understood, each of the form 2^p-1(2^p-1), where both p and 2^p-1 are prime numbers (no divisor other than 1 and themselves).

Unfortunately, it is difficult to tell for which primes p the number 2^p-1 is also prime; we don't even know whether there are infinitely many such primes p. Thus, we don't know if there are infinitely many perfect numbers, either.

Are there any odd perfect numbers? Major brainpower has been expended on this problem, over centuries, yet it remains tantalizingly open. Warning: If you are trying to find an odd perfect number by computer, please know that all odd numbers with 300 or fewer digits have already been checked.

Lots of information on perfect numbers is available from Wikipedia and other sources. My Dartmouth colleague Carl Pomerance, an expert in the area, can make a persuasive argument that odd perfect numbers probably don't exist. If you prove they don't exist, you will be famous!