Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have been trying to read a lot of literature concerning the above subject but I've not found anything useful to help my case.

Suppose you're given a linear diophantine in $a_1,a_2,\ldots,a_k$ where $k\leq 10$, and we are asked to tell if $a_1 x_1 + a_2 x_2 + \cdots+a_kx_k = N$ has a non negative solution or not?

We are given many such queries, so I think regular Euclid method wouldn't be sufficient.

Also,since I anyway brought the topic, could we utilise the calculation of the Frobenius Number of the equation to answer the above query.

share|cite|improve this question

One useful approach is to combine integer linear programming with lattice reduction, e.g. see Lichtblau: Integer Linear Programming, Frobenius Instances, and Frobenius Numbers

share|cite|improve this answer
Thank you for your help.I'd like to also add here another algorithm - "Round Robin Algorithm" which can help answer the MCP(Money Changing Problem) in constant time once we make a precomputation of the residual table.It is effective when the constraints are a little weak. – Ravi Kiran Feb 2 '11 at 20:49

Your Answer


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.