Difference between revisions of "2018 Putnam B Problems/Problem 3"
Pinotation (talk | contribs) (Created page with "==Problem== Find all positive integers <math>n < 10^{100}</math> for which simultaneously <math>n</math> divides <math>2^n</math>, <math>n-1</math> divides <math>2^n - 1</mat...") |
Pinotation (talk | contribs) (→See Also) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 4: | Line 4: | ||
==Solution== | ==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 | ||
| + | |||
| + | <math>\boxed{1, 2, 4,8}</math> | ||
| + | |||
| + | ~Pinotation | ||
| + | |||
| + | ==See Also== | ||
| + | |||
| + | [[2018 Putnam B Problems|2018 Putnam B Entire Test]] | ||
| + | |||
| + | [[2018 Putnam B Problems/Problem 2|2018 Putnam B Problem 2]] | ||
| + | |||
| + | [[2018 Putnam B Problems/Problem 4|2018 Putnam B Problem 4]] | ||
| + | |||
| + | {{MAA Notice}} | ||
Latest revision as of 18:24, 18 August 2025
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
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. 
