A fast method for finding the basis of non-negative solutions to a linear diophantine equation (Q1907269)

A method is given to solve \(\sum^N_{i=1} a_i x_i= \sum^M_{j=1} b_j y_j\), \(a_i, b_j, x_i, y_j\in \mathbb{N}\). At first the equation \(ax= by+ cz+ v\); \(a,b,c,x,y\in \mathbb{N}\), \(v\in \mathbb{Z}\) is considered and the solution with \((x,y, z)\) minimal in componentwise ordering are determined by using the congruence \(by+cz \equiv- v\pmod a\). Then the general problem is reduced to this case. The algorithm is extensively compared with other methods.