Video solution:

Click to load, then click again to play

Written solution:

Let $X=2^{17}$. Then $\dfrac{2^{289}+1}{2^{17}+1}=\dfrac{X^{17}+1}{X+1}=X^{16}-X^{15}+X^{14}-\cdots-X+1$.

Pair consecutive terms: $X^{16}-X^{15}$, $X^{14}-X^{13}$, $\ldots$, $X^2-X$, and then the final $+1$. Each pair is $2^{17m}(2^{17}-1)$, contributing $17$ ones in binary. There are $8$ such pairs plus the final $1$, so $k=8\cdot17+1=137$. Thus, C is the correct answer.