Some $k$ prime numbers $n_1, n_2, ..., n_k$ are given. Then some natural number $x$ is provided.

Then we want to figure natural numbers (including zero) $m_1, m_2, ..., m_k$ so that $n_1m_1 + n_2m_2 + ... + n_km_k = x$.

1) Suppose that for given $k$ and given sequence $n_k$, $x$ can be linearly decomposed as above. Then what would be the general algorithm for doing this? Note that I want cases for all possible $k$ from 2 to any number less than infinity.

2) As $k$ increases, would the number of possible cases of sequence $m_k$ decrease?

  • $\begingroup$ Are the $m_i$ allowed to be negative? If so this can always be done using just two primes by the Division Algorithm. $\endgroup$ May 21 '13 at 0:24
  • $\begingroup$ @AlexBecker The question specifies "natural numbers (including zero)", so the $m_i$ can't be negative. $\endgroup$
    – 6005
    May 21 '13 at 0:36
  • $\begingroup$ @AlexBecker I would rather prefer natural numbers. But anyway. Um. I am not sure how division algorithm would be used here. $\endgroup$
    – IDEO
    May 21 '13 at 0:36
  • $\begingroup$ He's really refering to Bezout's idenitity. You can solve linear diaphontine equations by using the Euclidian algorithm again and again until you have computed the gcd, then substitute back up. Recall that Gcd(a,b,c)=gcd(a,gcd(b,c)), ect. Here you'll get solutions in $\mathbb{Z}$, but you can search through them to get the natural solutions. You end up rewriting 1(=gcd of primes) through this process, but you can multiply by x to get what you want. $\endgroup$ May 21 '13 at 1:17

Since you allow $m_i=0$ you can let $m_3=m_4=\cdots=m_k=0$ and decompose $x$ using only $n_1,n_2$.

Since $n_1,n_2$ are primes $n_2$ has an inverse modulo $n_1$ and there is a number $0\le r<n_1$ that satisfies $$ rn_2 \equiv x \pmod{n_1} $$ If $x\ge rn_2$ then $x=rn_2 + cn_1$ for $c\ge 0$ and we are done.

Since $r\le n_1-1$ this suffices to provide a decomposition for every $x\ge (n_1-1)n_2$.

For $x<(n_1-1)n_2$ you can check if $x=cn_i$, if $x=cn_1 + n_i$ or if $x=cn_i + n_j$ for any $i,j$ to handle some cases. But I don't think there's an efficient general solution for all cases, because it seems to be an optimization version of the knapsack problem which is hard.

As $k$ increases the number of possible cases cannot decrease, because every solution $k=k_1<k_2$ gives a solution with $k=k_2$ with $m_i=0$ for $k_1<i\le k_2$.

If we constrain the $m_i>0$ then we cannot get a solution for any $x<\sum n_i$, but for $x\ge \sum n_i$ we can write $$ x' = x - \sum n_i \\ m_i' = m_i-1 $$ then it's just a rephrasing of the problem; a solution for $x'$ with $m_i'\ge 0$ gives a solution for $x$ with $m_i>0$. With this constraint the number of possible solutions as $k$ increases does eventually decrease, since for $k$ large enough $\sum n_i > x$ and solutions are no longer possible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.