For given positive integers $n,k$ prove that there always exists some positive integer $x$ for which $2^n\mid \dfrac{x(x+1)}{2}-k$

Question

For given positive integers $n,k$ prove that there always exists some $x$ for which $2^n \mid \dfrac{x(x+1)}{2}-k.$

My work:
$\dfrac{x(x+1)}{2}$ is the sum of all positive integers upto $x$.
Now, if we can show,
$\dfrac{x(x+1)}{2}\equiv 0,1,\ldots,2^n-1 \mod2^n$ then we are done.
Now, two cases arise,
(i) $x=2j \implies j(2j+1)\equiv 0,1,\ldots,2^n-1$
(ii) $x+1=2j \implies j(2j-1)\equiv 0,1,\ldots,2^n-1$
Now, I have reached a deadlock. Please help.

Answer 1

$$P_{n,k}(x) \equiv 2^n | \frac{x^2 + x}2 - k$$

By mechanical inspection we can see that the $x$ which satisfy $P_{n,k}$ this are all of the form $x_z = z\cdot 2^{n+1} + B$. So it suggests that we should consider this equation this equation in modulo $2^{n+1}$.

Consider possible solutions of the form $x = B \pmod {2^{n+1}}$:

$$2^n = \frac {B^2 + B} 2 - k \pmod {2^{n + 1}}$$

$$B^2 + B - 2k = 0 \pmod {2^{n+1}}$$

So we only have to show that this polynomial always has a solution in $B$. Induct on increasing $n$.

The base case for $n = 1$, $B^2 + B - 2k = 0 \pmod {4}$ finds solutions by a checking the 4 possible values of $k$.

The inductive case follows from Hensel's Lemma.

More detailed information is available from this XKCD thread.