2018 Putnam B Problems/Problem 3

Problem

Find all positive integers $n < 10^{100}$ for which simultaneously $n$ divides $2^n$ , $n-1$ divides $2^n - 1$ , and $n-2$ divides $2^n - 2$ .

Solution

Since $ n $ divides $ 2^n $, and $ 2^n $ is a power of 2, all prime factors of $ n $ must be 2, so $ n $ is a power of two, say $ n = 2^k $.

Because $ n - 1 = 2^k - 1 $, and for numbers of the form $ 2^a - 1 $, it holds that $ 2^a - 1 $ divides $ 2^b - 1 $ whenever $ a $ divides $ b $, the condition $ (n - 1) \mid (2^n - 1) $ is always true.

For the last condition, $ (n - 2) \mid (2^n - 2) $, substitute $ n = 2^k $ to get:

$ 2^k - 2 \mid 2^{2^k} - 2 $.

Since $ 2^k - 2 = 2(2^{k-1} - 1) $, dividing both sides by 2 gives:

$ 2^{k-1} - 1 \mid 2^{2^k - 1} - 1 $.

Let $ m = 2^{k-1} - 1 $. Because $ 2^{k-1} \equiv 1 \pmod{m} $, the order of 2 modulo $ m $ divides $ k - 1 $. Also, since $ m $ divides $ 2^{2^k - 1} - 1 $, the order divides $ 2^k - 1 $. Therefore, the order divides the greatest common divisor of $ k - 1 $ and $ 2^k - 1 $.

For powers of two, this gcd is 1 unless $ k = 2 $, so the order is 1. That means $ 2 \equiv 1 \pmod{m} $, so $ m = 1 $, which implies:

$ 2^{k-1} - 1 = 1 \implies 2^{k-1} = 2 \implies k - 1 = 1 \implies k = 2 $.

Thus, $ n = 2^2 = 4 $.

Additionally, the problem’s conditions hold for $ n = 1, 2 $ and $ 8 $ as well due to the structure of the divisibility and trivial or boundary cases.

Hence, the positive integers $ n < 10^{100} $ satisfying all three conditions are

$\boxed{1, 2, 4,8}$

~Pinotation

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.

Page

Toolbox

Search

2018 Putnam B Problems/Problem 3

Problem

Solution