Partitioning $\{1,2,\ldots,k\}$ into $p$ subsets with equal sums, where $p$ is prime

Question

Let $p$ be a prime natural number. For which positive integer $k$ can the set $\{1,2,\ldots,k\}$ be partitioned into $p$ subsets with equal sums of elements ?

Obviously, $p\mid k(k+1)$. Hence, $p\mid k$ or $p\mid k+1$. All we have to do now is to show a construction. But I can't find one. I have tried partitioning the set and choose one element from each set but that hasn't yielded anything.

Any hint will be appreciated.

Answer 1

Definition. For a prime natural number $p$, we say that a positive integer $k$ is $p$-splittable if $\{1,2,\ldots,k\}$ can be partitioned into $p$ subsets with the same sum.

If $p=2$, then it follows that $$\text{$k\equiv 0\pmod{4}$ or $k\equiv -1\pmod{4}$}\,.$$ For an odd prime $p$, we have $$\text{$k\equiv 0\pmod{p}$ or $k\equiv-1\pmod{p}$}\,.$$ It can be easily seen that, for $k\in\mathbb{N}$ and for any prime natural number $p$, if $k$ is $p$-splittable, then $k+2p$ is $p$-splittable (by adding $$\text{$\{k+1,k+2p\}$, $\{k+2,k+2p-1\}$, $\ldots$, $\{k+p,k+p+1\}$}$$ to the $p$ partitioning sets of $\{1,2,\ldots,k\}$).

Since $k=3$ and $k=4$ are $2$-splittable, any natural number of the form $4t-1$ or $4t$, where $t\in\mathbb{N}$, is $2$-splittable, and no other number is $2$-splittable. Also, for any odd prime natural number $p$, $k=2p-1$ and $k=2p$ are $p$-splittable, which means that any natural number of the form $2pt-1$ or $2pt$, where $t\in\mathbb{N}$, is $p$-splittable. Clearly, $k=p-1$ and $k=p$ are not $p$-splittable for odd $p$. We, however, claim that $k=3p-1$ or $k=3p$ are $p$-splittable for odd $p$, which would then imply that any natural number of the form $pt-1$ or $pt$ where $t\geq 2$ is an integer is $p$-splittable, and nothing else is $p$-splittable.

First, assume that $p\equiv 1\pmod{4}$, say $p=4r+1$ for some $r\in\mathbb{N}$.

• If $k=3p-1=12r+2$, then consider the partition of $\{1,2,\ldots,k\}$ into $$\text{$\{6r+1,12r+2\}$, $\{6r+2,12r+1\}$, $\ldots$, $\{9r+1,9r+2\}$}\,,$$ $$\text{$\{1,2,3,6r-2,6r-1,6r\}$, $\{4,5,6,6r-5,6r-4,6r-3\}$}\,,$$ $$\text{$\ldots$, $\{3r-2,3r-1,3r,3r+1,3r+2,3r+3\}$}\,.$$
• If $k=3p=12r+3$, then consider the partition $$\text{$\{6r+3,12r+3\}$, $\{6r+4,12r+2\}$, $\ldots$, $\{9r+2,9r+4\}$}\,,$$ $$\text{$\{1,2,3,6r-1,6r,6r+1\}$, $\{4,5,6,6r-4,6r-3,6r-2\}$}\,,$$ $$\text{$\ldots$, $\{3r-2,3r-1,3r,3r+2,3r+3,3r+4\}$, $\{3r+1,6r+2,9r+3\}$}\,.$$

Now, assume that $p\equiv -1\pmod{4}$, say $p=4r-1$ for some $r\in\mathbb{N}$.

• If $k=3p-1=12r-4$, then consider the partition $$\text{$\{6r-2,12r-4\}$, $\{6r-1,12r-5\}$, $\ldots$, $\{9r-4,9r-2\}$}\,,$$ $$\text{$\{1,2,3,6r-5,6r-4,6r-3\}$, $\{4,5,6,6r-8,6r-7,6r-6\}$}\,,$$ $$\text{$\ldots$, $\{3r-5,3r-4,3r-3,3r+1,3r+2,3r+3\}$, $\{3r-2,3r-1,3r,9r-3\}$}\,.$$
• If $k=3p=12r-3$, then consider the partition $$\text{$\{6r,12r-3\}$, $\{6r+1,12r-4\}$, $\ldots$, $\{9r-2,9r-1\}$}\,,$$ $$\text{$\{1,2,3,6r-4,6r-3,6r-2\}$, $\{4,5,6,6r-7,6r-6,6r-5\}$}\,,$$ $$\text{$\ldots$, $\{3r-5,3r-4,3r-3,3r+2,3r+3,3r+4\}$, $\{3r-2,3r-1,3r,3r+1,6r-1\}$}\,.$$

Question. What if $p$ is not prime? I conjecture the following:

(1) If $p$ is odd, then, for any $j\in\{-1,0,1,2,\ldots,p-2\}$ such that $p\mid j(j+1)$, every integer of the form $tp+j$, where $t\geq 2$ is an integer, is $p$-splittable, and nothing else is $p$-splittable.

(2) If $p$ is even, then, for any $j\in\{-1,0,1,2,\ldots,2p-2\}$ such that $p\mid \dfrac{j(j+1)}{2}$, every integer of the form $2tp+j$, where $t\in\mathbb{N}$, is $p$-splittable, and nothing else is $p$-splittable.

This question is also posted here: $p$-Splittable Integers.