Linear Diophantine equations are Diophantine equations of the form A_{1}x_{1} + A_{2}x_{2} + ... + A_{n}x_{n}= B, where all A_{j} and B are integers and each x_{j} is an unknown integer. They are used discrete mathematics and in integer programming in particular, such as the following system of equations:

/ x + y + z = 25

| 7x + 12y + 3z = 150

\ 2x + y + 13z = max.

A linear Diophantine equation has no solutions if gcd(A_{1}, A_{2}, ..., A_{n}) does not divide B. Otherwise, the solution proceeds as follows:

(Assuming you've done some algebra to narrow the system of equations down to a single Ax + By = C.)
- Divide through by gcd(A,B) to get a reduced equation Dx + Ey = F. [gcd(D,E)=1]
- Solve either of these guys for integers:

a) x = (F - Ey) / D where y is in {0, 1, 2, ..., (D-1)}
b) y = (F - Dx) / E where x is in {0, 1, 2, ..., (E-1)}

- The resulting (x,y) is a particular solution of the equation.

To illustrate how to solve for a general solution of the equation, the solution to 5x + 7y = 10 is given:

- x = (10 - 7y) / 5
- For y = 0, x = 2; therefore (2,0) is a particular solution.
5x + 7y = 10
- 5(2) + 7(0) = 10 We plug in our particular solution here.
----------------------
5(x-2) + 7(y-0) = 0 =====>5(x-2) = -7(y-0)

- Then, (x-2) is divisible by -7, and (y-0) = y is divisible by 5. This means y = 5q and x = -7q + 2 for any integer q.
- To find other solutions besides (2,0) just plug in different integers for q.