CODEWITHSUNDEEP
algorithmmathequationdiophantine
user2129227
user2129227

Reputation: 97

Count number of solutions for multiple-variiable linear diophantine equations with coprime coefficient

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.

Upvotes: 3

Views: 967

Answers (1)

Udo Klein
Udo Klein

Reputation: 6902

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.

Upvotes: 1

Related Questions