CHAPTER 7

Solving Diophantine equations

Several topics discussed in this lecture have required solving Diophantine equations (e.g., Sections 2.3.2 and 6.1). Diophantine equations are equations whose domain, range and coefficients are integers and whose form is that of an indeterminate (i.e., it has infinite solutions) polynomial. The equations we are interested in are polynomials of degree one in possibly many variables, which are often referred to as affine equations. This chapter may be skipped, or quickly scanned, by most readers, but is provided for the reader desiring a deeper understanding of the mechanics behind solving Diophantine equations.

7.1 SOLVING SINGLE DIOPHANTINE EQUATIONS

Let the Diophantine equation we wish to solve be in the variables i₁, i₂, . . . , i_n, and of the form:

We can form a coefficient matrix A of the equation:

where the j’th row of A is the coefficient for the j’th variable in the system. The left-hand side of the system, C, can be similarly represented. Because our system only has one equation, this is simply:

To solve the system of equations, we first form the matrix IA, where I is the identity matrix. This gives the matrix

An elimination algorithm, reminiscent of Gaussian elimination but using only integer operations, can be applied to the matrix to obtain the matrix UD:

The resulting U matrix is an n × n matrix, and the resulting D matrix contains the greatest common divisor (or gcd) of the coefficients for the equation as its first element.

Let T = [t₁, t₂, . . . , t_n] be a vector of n parameters. Then TD = C, i.e., in our equation, c₀ = d₁t₁, and by simple algebra, t₁ = d/d₁. The equation has a solution if and only if d₁ evenly divides c, i.e., if the gcd of the coefficients evenly divides the constant term. If a solution does exist, then

and the relationship

holds. Stated more verbosely,

By substituting the solutions for t₁ and arbitrary integer values for t_k, 1 < k ≤ n into the system of Equation 7.2, all solutions to Equation 7.1 can be found.

7.2 SOLVING MULTIPLE DIOPHANTINE EQUATIONS

It is sometimes desirable to simultaneously solve a system of Diophantine equations. A general system of Diophantine equations can be expressed as:

This set of equations can be represented in matrix form as:

or, more generally, iA = C and the unique solution to this equation can be found as i = CA⁻¹.

The goal in solving such system is the same as when using Gaussian elimination—we wish to reduce the array and find an upper triangular array that can be used to solve for each of the n variables in turn. However, because we are working with Diophantine equations, and we want them to remain Diophantine equations throughout the process, we avoid the use of division in the elimination process. Two types of operations will be performed on the matrix, interchange of two rows r_p, r_q and replacement of a row r_p by r_p − kr_q. By performing these operations repeatedly, the matrix is reduced to an upper triangular form.

We now describe how to do this systematically, additional details can be found in [24]. Consider the n × m matrix of integers, A, above. It can be augmented with an n × n identity matrix I, yielding the matrix

We repeatedly apply the operations of Section 7.1 to eliminate various elements of the A matrix until the upper triangular form is achieved. At this point we have an n × m upper triangular transformed matrix A and a n × n Unimodular matrix U that is the result of applying the operations forming the upper triangular A matrix to the I matrix. As in the previous section, x = TU. The the parametric solutions of the system of Diophantine equations can be found by multiplying the vector [c′, t₂, t₃, . . . , t_n] times U. An example is given in Figure 7.1.

7.3 EXTREME VALUES OF INTEGER FUNCTIONS

It is often the case that it is desirable to find the minimum and maximum values that an affine expression can assume. In this section we will show how to find the value of the expression

where, as above, the a_k are integer constants and the i_k are integer variables. For each i_k we assume there are integer bounds such that L_ik ≤ i_k ≤ U_ik. For additional details, see [24].

We first provide two definitions.

Definition 7.1 The positive part of a number a, denoted a⁺, is a when a ≥ 0, and is 0 otherwise.

Figure 7.1: An example of solving a Diophantine equation and expressing its solution in terms of parametric terms.

Definition 7.2 The negative part of a number a, denoted a⁻, is |a| when a ≥ 0, and is 0 otherwise.

Thus, the negative and positive parts of a number return the magnitude of the number when it is a negative, and positive number, respectively. Using these concepts, we can succinctly express the extreme values of the expression. The lower bound of the expression can be

and

Intuitively, when computing the lower (upper) bound we want to minimize (maximize) the value of each term. To minimize a term when the coefficient a_k is positive requires using the lowest value i_k can take on, and when the coefficient a_k is negative using the largest value of i_k, and when a_k is positive using the smallest value of i_k. The maximum value is done in a similar, and symmetric, way.