finding out linear decomposition of $x$ into $k$ prime numbers 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?
 A: 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.
