Determine all possible integers n less than 10
100 that simultaneously satisfy these conditions:
- n divides 2n
- n - 1 divides 2n - 1
- n - 2 divides 2n - 2
Note: As an extra challenge, determine a semi-analytic (simple calculator + p&p) solution to this problem.
**** Adapted from a problem appearing at a William Lowell Putnam Mathematics Competition
Lets start with the first condition: n | 2^n. Then n is a power of 2.
Then let n=2^m
Then the second condition becomes 2^m-1 | 2^(2^m)-1. These are both of the form x^a-1, so then the exponents also divide. Then m | 2^m.
Then let m=2^L.
Then the third condition becomes 2^(2^L) - 2 | 2^(2^(2^L)) - 2
Divide out a common factor of 2: 2^(2^L-1) - 1 | 2^(2^(2^L)-1) - 1
Then the exponents divide: 2^L-1 | 2^(2^L)-1
And again exponents divide: L | 2^L
Let L=2^k
Now back-substitute to get n = 2^(2^(2^k)).
At k=0 then n=4
At k=1 then n=16
At k=2 then n=65536
At k=3 then n=2^65536~=10^19728, far larger than 10^100
Thus the integers satisfying the conditions under 10^100 are 4, 16, and 65536.
Solution
