3

Let the general diophantine equation be : a1*x1 + a2*x2 + .... + am*xm = n , where gcd(a1...am) = 1, (a1....am) >= 0

I want to find the number of non-negative (x1..xm) solutions. Could someone help me with this? Detailed mathematical explanations or algorithms will help very much.

user2129227
  • 97
  • 1
  • 4
  • 2
    If there's no programming language in your tags, you should ask yourself whether this really belongs on stack overflow. – antonijn Mar 03 '13 at 16:43
  • The number of nonzero solutions is infinite, since you can always add multiples of a2 to x1 and subtract the corresponding multiple of a1 from x2. Or are you looking for non-negative solutions? – Daniel Fischer Mar 03 '13 at 16:43
  • only non-negative solutions. Sorry I edited the questions – user2129227 Mar 04 '13 at 09:58

1 Answers1

1

What you are searching for is known as "smith normal form". It is explained e.g. at wikipedia: http://en.wikipedia.org/wiki/Smith_normal_form The wikipedia entry also explains the standard algorithm for this kind of problem.

In you special case this is basically the euclidian gcd algorithm.

Udo Klein
  • 6,784
  • 1
  • 36
  • 61