# 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.

• If $n$ is an integer, then $T_{2n}=1+2+\cdots +2n=n\times (2n+1)$ so $(2n+1)$ is a trivial bound on your solution for $k$.
– lulu
Apr 18, 2020 at 12:13
• If $n$ is odd, a solution is given by $k=(n-1)/2$ and $x=n-1$. Apr 18, 2020 at 12:20
• Is there any use to the fact that $8nk+1=(2x+1)^2$? Apr 18, 2020 at 13:33
– lhf
Apr 18, 2020 at 13:38

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.
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$$.