Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Are the $m_i$ allowed to be negative? If so this can always be done using just two primes by the Division Algorithm. –  Alex Becker May 21 '13 at 0:24
    
@AlexBecker The question specifies "natural numbers (including zero)", so the $m_i$ can't be negative. –  Goos May 21 '13 at 0:36
    
@AlexBecker I would rather prefer natural numbers. But anyway. Um. I am not sure how division algorithm would be used here. –  IDEO May 21 '13 at 0:36
    
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. –  Chris Dugale May 21 '13 at 1:17

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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