Editing Diophantine equation (section)

=== System of linear Diophantine equations===
More generally, every system of linear Diophantine equations may be solved by computing the [[Smith normal form]] of its matrix, in a way that is similar to the use of the [[reduced row echelon form]] to solve a [[system of linear equations]] over a field. Using [[matrix (mathematics)#Notation|matrix notation]] every system of linear Diophantine equations may be written
<math display=block>AX = C,</math>
where {{mvar|A}} is an {{math|''m'' × ''n''}} matrix of integers, {{mvar|X}} is an {{math|''n'' × 1}} [[column matrix]] of unknowns and {{mvar|C}} is an {{math|''m'' × 1}} column matrix of integers.

The computation of the Smith normal form of {{mvar|A}} provides two [[unimodular matrix|unimodular matrices]] (that is matrices that are invertible over the integers and have ±1 as determinant) {{mvar|U}} and {{mvar|V}} of respective dimensions {{math|''m'' × ''m''}} and {{math|''n'' × ''n''}}, such that the matrix
<math display=block>B = [b_{i,j}] = UAV</math>
is such that {{mvar|b<sub>i,i</sub>}} is not zero for {{mvar|i}} not greater than some integer {{mvar|k}}, and all the other entries are zero. The system to be solved may thus be rewritten as
<math display=block>B (V^{-1}X) = UC.</math>
Calling {{mvar|y<sub>i</sub>}} the entries of {{math|''V''{{i sup|−1}}''X''}} and {{mvar|d<sub>i</sub>}} those of {{math|1=''D'' = ''UC''}}, this leads to the system
<math display=block>\begin{align}
& b_{i,i}y_i = d_i, \quad 1 \leq i \leq k \\
& 0y_i = d_i, \quad k < i \leq n.
\end{align}</math>

This system is equivalent to the given one in the following sense: A column matrix of integers {{mvar|x}} is a solution of the given system if and only if {{math|1=''x'' = ''Vy''}} for some column matrix of integers {{mvar|y}} such that {{math|1=''By'' = ''D''}}.

It follows that the system has a solution if and only if {{mvar|b<sub>i,i</sub>}} divides {{mvar|d<sub>i</sub>}} for {{math|''i'' ≤ ''k''}} and {{math|1=''d<sub>i</sub>'' = 0}} for {{math|''i'' > ''k''}}. If this condition is fulfilled, the solutions of the given system are
<math display=block> V\,
\begin{bmatrix}
\frac{d_1}{b_{1,1}}\\
\vdots\\
\frac{d_k}{b_{k,k}}\\
h_{k+1}\\
\vdots\\
h_n
\end{bmatrix}\,, </math>
where {{math|''h''<sub>''k''+1</sub>, …, ''h<sub>n</sub>''}} are arbitrary integers.

[[Hermite normal form]] may also be used for solving systems of linear Diophantine equations. However, Hermite normal form does not directly provide the solutions; to get the solutions from the Hermite normal form, one has to successively solve several linear equations. Nevertheless, Richard Zippel wrote that the Smith normal form "is somewhat more than is actually needed to solve linear diophantine equations. Instead of reducing the equation to diagonal form, we only need to make it triangular, which is called the Hermite normal form. The Hermite normal form is substantially easier to compute than the Smith normal form."<ref name="Zippel1993">{{cite book|author=Richard Zippel|title=Effective Polynomial Computation|year=1993|publisher=Springer Science & Business Media|isbn=978-0-7923-9375-7|page=50}}</ref>

[[Integer linear programming]] amounts to finding some integer solutions (optimal in some sense) of linear systems that include also [[inequation]]s.  Thus systems of linear Diophantine equations are basic in this context, and textbooks on integer programming usually have a treatment of systems of linear Diophantine equations.<ref>{{cite book|editor=John Alan Robinson and Andrei Voronkov|title=Handbook of Automated Reasoning Volume I|year=2001|publisher=Elsevier and MIT Press|id= (Elsevier) (MIT Press)|author=Alexander Bockmayr, Volker Weispfenning|chapter=Solving Numerical Constraints|page=779|isbn=0-444-82949-0}}</ref>