Putnam

The minimum is $3$. $\text{First}$ solution.} We record the factorization $2023 = 7\cdot 17^2$. We first rule out $k(n)=1$ and $k(n)=2$. If $k(n)=1$, then $2023n = 2^a$ for some $a$, which clearly cannot happen. If $k(n)=2$, then $2023n=2^a+2^b=2^b(1+2^{a-b})$ for some $a>b$. Then $1+2^{a-b} \equiv 0\pmod{7}$; but $-1$ is not a power of $2$ mod $7$ since every power of $2$ is congruent to either $1$, $2$, or $4 \pmod{7}$. We now show that there is an $n$ such that $k(n)=3$. It suffices to find $a>b>0$ such that $2023$ divides $2^a+2^b+1$. First note that $2^2+2^1+1=7$ and $2^3 \equiv 1 \pmod{7}$; thus if $a \equiv 2\pmod{3}$ and $b\equiv 1\pmod{3}$ then $7$ divides $2^a+2^b+1$. Next, $2^8+2^5+1 = 17^2$ and $2^{16\cdot 17} \equiv 1 \pmod{17^2}$ by Euler's Theorem; thus if $a \equiv 8 \pmod{16\cdot 17}$ and $b\equiv 5 \pmod{16\cdot 17}$ then $17^2$ divides $2^a+2^b+1$. We have reduced the problem to finding $a,b$ such that $a\equiv 2\pmod{3}$, $a\equiv 8\pmod{16\cdot 17}$, $b\equiv 1\pmod{3}$, $b\equiv 5\pmod{16\cdot 17}$. But by the Chinese Remainder Theorem, integers $a$ and $b$ solving these equations exist and are unique mod $3\cdot 16\cdot 17$. Thus we can find $a,b$ satisfying these congruences; by adding appropriate multiples of $3\cdot 16\cdot 17$, we can also ensure that $a>b>1$. $\text{Second}$ solution.} We rule out $k(n) \leq 2$ as in the first solution. To force $k(n) = 3$, we first note that $2^4 \equiv -1 \pmod{17}$ and deduce that $2^{68} \equiv -1 \pmod{17^2}$. (By writing $2^{68} = ((2^4+1) - 1)^{17}$ and expanding the binomial, we obtain $-1$ plus some terms each of which is divisible by 17.) Since $(2^8-1)^2$ is divisible by $17^2$, $$\begin{align*} 0 &\equiv 2^{16} - 2\cdot 2^8 + 1 \equiv 2^{16} + 2\cdot 2^{68}\cdot 2^8 + 1 \\ &= 2^{77} + 2^{16} + 1 \pmod{17^2}. \end{align*}$$ On the other hand, since $2^3 \equiv -1 \pmod{7}$, $$2^{77} + 2^{16} + 1 \equiv 2^2 + 2^1 + 1 \equiv 0 \pmod{7}.$$ Hence $n = (2^{77}+2^{16}+1)/2023$ is an integer with $k(n) = 3$. $\text{Remark.}$ A short computer calculation shows that the value of $n$ with $k(n)=3$ found in the second solution is the smallest possible. For example, in SageMath, this reduces to a single command: $\text{}$ assert all((2^a+2^b+1) % 2023 != 0 for a in range(1,77) for b in range(1,a)) $\text{}$