Are There Infinitely Many?
Are there infinitely many positive integers n such that n divides (that is, is a factor of) the number 2^(n)+1?
Solutions are due by Thursday, Oct 3rd at 5:00 PM. Please submit all solutions to mathpotw@acu.edu.
Solution to Are There Infinitely Many?
A manual check discovers that n divides 2n + 1 for n = 1, 3, and 9. This is enough to cause a person to check the number n = 27 and find that it works also. So let’s proceed, using a proof by induction, to show that 3k divides 23k + 1 for every nonnegative integer k.
We have observed that the statement is true for k = 0. Now suppose that it is true for some integer k >= 0 and use this supposition to show that 3k+1divides 23k+1 + 1. But 23k+1 + 1 can be rewritten as (23k)3 + 1, an expression of the form x3 + 1, and this can be factored into (x + 1)(x2 – x + 1). So we let x = 23k and observe that by the induction hypothesis, 3k divides (x + 1). All that remains is to find a factor of 3 in the term (x2 – x + 1). But
(x2 – x + 1) = ((x+1)2 – 2x – 1 – x + 1) = ((x+1)2 – 3x).Now we see that 3 is a factor of (x2 – x + 1) because of the induction hypothesis again. The proof is done.
