(en.wikipedia.org) Diophantine equation - Wikipedia
ROAM_REFS: https://en.wikipedia.org/wiki/Diophantine_equation
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates the sum of two or more unknowns, with coefficients, to a constant. An exponential Diophantine equation is one in which unknowns can appear in exponents.
Diophantine problems have fewer equations than unknowns and involve finding integers that solve simultaneously all equations. Because such systems of equations define algebraic curves, algebraic surfaces, or, more generally, algebraic sets, their study is a part of algebraic geometry that is called Diophantine geometry.
The word Diophantine refers to the Hellenistic mathematician of the 3rd century, Diophantus of Alexandria, who made a study of such equations and was one of the first mathematicians to introduce symbolism into algebra. The mathematical study of Diophantine problems that Diophantus initiated is now called Diophantine analysis.
While individual equations present a kind of puzzle and have been considered throughout history, the formulation of general theories of Diophantine equations, beyond the case of linear and quadratic equations, was an achievement of the twentieth century.
(en.wikipedia.org) Linear Diophantine equations - Diophantine equation - Wikipedia
ROAM_REFS: https://en.wikipedia.org/wiki/Diophantine_equation#Linear_Diophantine_equations
* One equation
The simplest linear Diophantine equation takes the form \[ax + by = c,\] where a, b and c are given integers. The solutions are described by the following theorem:
This Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b. Moreover, if (x, y) is a solution, then the other solutions have the form (x + kv, y − ku), where k is an arbitrary integer, and u and v are the quotients of a and b (respectively) by the greatest common divisor of a and b.
Proof: If d is this greatest common divisor, Bézout's identity asserts the existence of integers e and f such that ae + bf = d. If c is a multiple of d, then c = dh for some integer h, and (eh, fh) is a solution. On the other hand, for every pair of integers x and y, the greatest common divisor d of a and b divides ax + by. Thus, if the equation has a solution, then c must be a multiple of d. If a = ud and b = vd, then for every solution (x, y), we have \[\begin{matrix} {a(x + kv) + b(y - ku)} & {= ax + by + k(av - bu)} \\ & {= ax + by + k(udv - vdu)} \\ & {= ax + by,} \end{matrix}\] showing that (x + kv, y − ku) is another solution. Finally, given two solutions such that \[ax_{1} + by_{1} = ax_{2} + by_{2} = c,\] one deduces that \[u(x_{2} - x_{1}) + v(y_{2} - y_{1}) = 0.\] As u and v are coprime, Euclid's lemma shows that v divides /x/2 − /x/1, and thus that there exists an integer k such that both \[x_{2} - x_{1} = kv,\quad y_{2} - y_{1} = - ku.\] Therefore, \[x_{2} = x_{1} + kv,\quad y_{2} = y_{1} - ku,\] which completes the proof.
* Chinese remainder theorem
The Chinese remainder theorem describes an important class of linear Diophantine systems of equations: let \(n_{1},\ldots,n_{k}\) be k pairwise coprime integers greater than one, \(a_{1},\ldots,a_{k}\) be k arbitrary integers, and N be the product \(n_{1}\cdots n_{k}.\) The Chinese remainder theorem asserts that the following linear Diophantine system has exactly one solution \((x,x_{1},\ldots,x_{k})\) such that 0 ≤ x < N, and that the other solutions are obtained by adding to x a multiple of N: \[\begin{matrix} x & {= a_{1} + n_{1}\, x_{1}} \\ & {\;\; \vdots} \\ x & {= a_{k} + n_{k}\, x_{k}} \end{matrix}\]
* 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 notation every system of linear Diophantine equations may be written \[AX = C,\] where A is an m × n matrix of integers, X is an n × 1 column matrix of unknowns and C is an m × 1 column matrix of integers.
The computation of the Smith normal form of A provides two unimodular matrices (that is matrices that are invertible over the integers and have ±1 as determinant) U and V of respective dimensions m × m and n × n, such that the matrix \[B = \lbrack b_{i,j}\rbrack = UAV\] is such that bi,i is not zero for i not greater than some integer k, and all the other entries are zero. The system to be solved may thus be rewritten as \[B(V^{- 1}X) = UC.\] Calling yi the entries of V/−1/X and di those of D = UC, this leads to the system \[\begin{matrix} & {b_{i,i}y_{i} = d_{i},\quad 1 \leq i \leq k} \\ & {0y_{i} = d_{i},\quad k < i \leq n.} \end{matrix}\]
This system is equivalent to the given one in the following sense: A column matrix of integers x is a solution of the given system if and only if x = Vy for some column matrix of integers y such that By = D.
It follows that the system has a solution if and only if bi,i divides di for i ≤ k and di = 0 for i > k. If this condition is fulfilled, the solutions of the given system are \[V\,\begin{bmatrix} \frac{d_{1}}{b_{1,1}} \\ \vdots \\ \frac{d_{k}}{b_{k,k}} \\ h_{k + 1} \\ \vdots \\ h_{n} \end{bmatrix}\,,\] where h//k/+1, …, /hn 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."
Integer linear programming amounts to finding some integer solutions (optimal in some sense) of linear systems that include also inequations. 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.