Linear Diophantine equations are Diophantine equations of the form A1x1 + A2x2 + ... + Anxn= B, where all Aj and B are integers and each xj 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(A1, A2, ..., An) 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.)
  1. Divide through by gcd(A,B) to get a reduced equation Dx + Ey = F. [gcd(D,E)=1]
  2. 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)}
    
  3. 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:

  1. x = (10 - 7y) / 5
  2. For y = 0, x = 2; therefore (2,0) is a particular solution.
  3.      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)
    
  4. 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.
  5. To find other solutions besides (2,0) just plug in different integers for q.