2018 Putnam B Problems/Problem 3

Problem

Find all positive integers for which simultaneously divides , divides , and divides .

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

~Pinotation

See Also

2018 Putnam B Entire Test

2018 Putnam B Problem 2

2018 Putnam B Problem 4

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