Putnam 2018 
Topic: Number Theory

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$. Compute the product of all such valid $n$ and determine the exponent of 2 in the final product as the final answer.

Solution: First, note that $n$ divides $2^n$ if and only if $n$ is itself a power of 2; we may thus write $n = 2^m$ and note that if $n<10^{100}$, then \[ 2^m = n < 10^{100} < (10^3)^{34} < (2^{10})^{34} = 2^{340}. \] Moreover, the case $m=0$ does not lead to a solution because for $n=1$, $n-1 = 0$ does not divide $2^n-1 = 1$; we  may thus assume $1 \leq m \leq 340$.  Next, note that modulo $n-1 = 2^m-1$, the powers of $2$ cycle with period $m$ (the terms $2^0, \dots, 2^{m-1}$ remain the same upon reduction, and then the next term repeats the initial 1); consequently, $n-1$ divides $2^n-1$ if and only if $m$ divides $n$, which happens if and only if $m$ is a power of 2. Write $m = 2^\ell$ and note that $2^\ell < 340 < 512$, so $\ell < 9$. The case $\ell=0$ does not lead to a solution because for $n=2$, $n-2 =0$ does not divide $2^n-2 = 2$; we may thus assume $1 \leq \ell \leq 8$.  Finally, note that $n-2 = 2^m-2$ divides $2^n-2$ if and only if $2^{m-1} - 1$ divides $2^{n-1} - 1$. By the same logic as the previous paragraph, this happens if and only if $m-1$ divides $n-1$, that is, if $2^\ell - 1$ divides $2^m-1$. This in turn happens if and only if $\ell$ divides $m = 2^\ell$, which happens if and only if $\ell$ is a power of 2. The values allowed by the bound $\ell < 9$ are $\ell = 1,2,4,8$; for these values, $m \leq 2^8 = 256$ and \[ n = 2^m \leq 2^{256} \leq (2^3)^{86} < 10^{86} < 10^{100}, \] so the solutions listed do satisfy the original inequality. The values of $n$ with this property are $2^{2^\ell}$ for $\ell = 1,2,4,8$, thus making the exponent of 2, $\boxed{278}$.