Let $n$ be any positive integer.

Let $p_1,p_2,...,p_m$ be any positive integers such that no more than one of the $p_i$s is $1$ and $\prod_{i=1}^mp_i=n$.

Finally, let $s_1,s_2,...,s_m$ be any nonnegative integers such that $\sum_{i=1}^ms_i=2n$.

Do there always exist nonnegative* integers $k_1,k_2,...,k_m$ such that: $$\sum_{i=1}^m(k_ip_i)=n$$

And, for each $i$: $$k_ip_i\leq s_i$$

Initially, I tried induction on $m$ (the number of factors, $p_i$). I assumed the hypothesis held for all cases when $m$ was less than $t$ for a fixed $n$ and tried proving it for the case of $m=t$ (for the same $n$) but got nowhere.

I also tried induction on the number of (not necessarily distinct) prime factors of $n$ but, again, only got past the base case.
(I couldn't really get past viewing this through an induction lens)

It seems as if it should be true given that the $s_i$'s need to sum to $2n$ whereas the $k_ip_i$'s need to sum to only $n$ (and the size of the $p_i$ terms are limited by the constraint that their product equal $n$) but I can't find a way to prove it (or a counterexample).

Are there any hints anyone can provide for a proof (or for generating a good counterexample)?

*EDIT: Originally, this question asked only about the existence of integer $k_i$s - the nonnegativity of these values was not considered, but it was expected that nonnegativity would emerge from a proof of the original question. A solution to the original question was found, but the approach taken did not seem to provide any leads for showing nonnegativity.

  • $\begingroup$ What is the source of this problem? $\endgroup$ Feb 28, 2019 at 19:24
  • $\begingroup$ @CarlSchildkraut Uh it kind of popped up out of a few different things. It's related to something I thought up while studying partitions under the framework of generating functions but I returned to this more specific version recently because it turned out to be related to a special case of a particular problem to do with groups. Always been a bit skeptical of (versions of) this problem, though. $\endgroup$ Feb 28, 2019 at 19:39

1 Answer 1


This is not an answer, it's a long comment.

Consider the number N=p∗q=7∗13=91. If you look at 91, it's the point in the multiplication table where the line $L_1$ of numbers with the same (p−q) meets the line $L_2$ with the same (p+q). $L_1$ starts at 7 and $L_2$ starts at 19 since p−q=13−7=7−1=6 and p+q=17+13=20=1+19. So you can write for N=91=7+9+11+13+15+17+19 but also N=19+17+15+13+11+9+7 depending on where you start. If you add both sums term by term you get $2N=182=(7+19)+(9+17)+(11+15)+(13+13)+(15+11)+(17+9)+(19+7)=7*(26)=7*2*13=2*(7*13). This can be done for any composite number.

The problem is we don't know (p−q) or (p+q) so we can't do that. So basically we can't use it since we don't even have a good approximation to (p−q) or (p+q).

For you summation $sum(k_ip_i)$, I think it cannot be done in general. you can write $N=91=13+13+13+13+13+13+13=13(1+1+1+1+1+1+1)=13*7$. Once a number $N$ is given, the factors are fixed, one p and one q for the case $N=pq$, so I am not sure you can sum up over $p_{i}$. However, because $91$ is a triangular number you can write it as a sum from $1$ to $13$ but in this case you don't need two variables $k_i$ and $p_i$.

  • 2
    $\begingroup$ With $m=2$, it is always possible: From $s_1+s_2=2n$, one of the $s_i$ must be $\ge n$. Then we can let $k_i=n/p_i$ for that $i$ and $k_j=0$ for the other index. $\endgroup$ Mar 14, 2019 at 13:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .