Finding a multiple of a given number which can be expressed as 1+2+...+x An unrelated problem I came across in the domain of computer science reduced to the following mathematical problem:
For a given number $ n\in \mathbb{N} $, I need to find if any multiple of that number can be expressed as a series of the first $x$ natural numbers. Further, if such multiples exist, I need to find the least such multiple.
That is, for a given $n$, I need the lowest values for $k, x$ that satisfy the equation:
$$
n \times k = \frac{x\times \left(x+1  \right)}{2}, n\in \mathbb{N}, k\in \mathbb{N}, x\in \mathbb{N}
$$
I understand that this is a diophantine equation, and while I could find ways to solve linear and quadratic diophantine equations, I could not find a general form that could be applied to the problem above, especially since there are two unknowns in the equation.
I also considered that one way to solve the problem would be to try and factorize $2 \times n$ into two consecutive numbers as indicated by the rearranged equation:
$$
k = \frac{x\times \left(x+1  \right)}{2 \times n}, n\in \mathbb{N}, k\in \mathbb{N}, x\in \mathbb{N}
$$
Finally, since the problem originated in the context of computer programs, I figured that if I couldn't find a mathematical approach to solve this equation, I could simply try for all values of x till I found an appropriate value. The problem with that approach (apart from the less than ideal computational time needed) is that I do not know if the $n$ I'm solving this for has such a multiple or not, hence I have no way of knowing if the brute-force algorithm would terminate.
So I also tried (unsuccessfully) to find a method to determine if such a value for $k, x$ exists for a given $n$. Does such a method exist?
I would appreciate any help in trying to solve this problem.
 A: The question whether such $x$ always exists has already been answered in the comments: $x=2n$ is a solution.
To find possible smaller solutions, you can proceed as follows. Let $2n=\prod_{k=1}^mp_k^{\alpha_k}$ be the prime factorization of $2n$, with $m$ distinct prime factors. Each prime power $p_k^{\alpha_k}$ must divide either $x$ or $x+1$ (since they cannot both be divisible by $p_k$). Thus there are $2^m$ different possibilities for splitting up the prime powers among $x$ and $x+1$. Let $r$ and $s$ be the products of the prime powers that divide $x$ and $x+1$, respectively. Then $x\equiv0\bmod r$ and $x\equiv-1\bmod s$. By the Chinese remainder theorem there is exactly one value $x$ with $1\le x\le rs=2n$ that satisfies these two congruences. It can be efficiently computed. So you just need to compute $2^m$ such values and take the lowest one.
Some examples:
For $n=5$, we have $2n=10=2^1\cdot5^1$, so there are $2^2=4$ ways to split up the two prime powers. Putting them all in $x$ yields $x=10$, putting them all in $x+1$ yields $x=9$, putting the $2$ in $x$ and the $5$ in $x+1$ yields $x=4$ and putting the $5$ in $x$ and the $2$ in $x+1$ yields $x=5$. These are indeed the four triangular numbers up to $x=10$ that are divisible by $5$, with the smallest at $x=4$.
For $n=18$, we have $2n=36=2^2\cdot3^2$, so again $2^2=4$ cases to try. Putting all factors in $x$ yields $x=36$, putting all factors in $x+1$ yields $x=35$, putting the $2$s in $x$ and the $3$s in $x+1$ yields $x\equiv0\bmod4$ and $x\equiv-1\bmod9$, with solution $x=8$, and putting the $3$s in $x$ and the $2$s in $x+1$ yields $x\equiv0\bmod9$ and $x\equiv-1\bmod4$, with solution $x=27$. These are indeed the four triangular numbers up to $x=36$ that are divisible by $18$, with the smallest at $x=8$.
