Number Theory: Diophantine Equations

Introduction

Diophantine Equations

From these equations, we have derived the following expressions:

840 611 = 1 +  229 611 = 1 +  1 611/229 ,  611 229 = 2 +  153 229 = 2+  1 229/153 ,  229 153 = 1 +  76 153 = 1 +  1 153/76 ,  153 76 = 2 +  1 76 . .

Combining these operations, we obtain the development of the rational
number [ 840/611] in the form

840 611 = 1 +  1 2 +  1 1 +  1 2 + [ 1/76] .

An expression of the form

a = a0 +  1 a1 +  1 a2 +  1 :+ [ 1/(an-1 + [ 1/(an)])]

where the a's are positive integers, is called a continued fraction. There are also non-terminating continued fractions, for irrational numbers like Ö2. A continued fraction expression for any number, rational or otherwise, can be obtained using the Euclidean algorithm, as above. Continued fractions are of great importance in the branch of mathematics called Diophantine analysis. A Diophantine equation is an algebraic equation in one or more unknowns with integer coefficients, for which integer solutions are sought. The solutions may be finite or infinite in number. The simplest case is the linear Diophantine equation in two unknowns:

ax + by = c

(1)

where a, b and c are given integers, and integer solutions x, y are desired. The complete solution of an equation of this form may be found as follows.

To begin with, we find d = (a, b) by the Euclidean algorithm. Then, by using (in reverse order) the sequence of equations in the algorithm, we can find integers k and l such that

ak + bl = d

(2)

Hence the equation (1) has a particular solution x = k,  y = l, for the case c = d. More generally, if c is any multiple of d, so that c = d·q, we obtain from (2):

a(kq) + b(lq) = dq = c

so that (1) has particular solution x = x^* = kq,  y = y^* = lq. Conversely, if (1) has any solutions, then c must be a multiple of d = (a, b). For d divides both a and b, so divides the left hand side of the equation, hence it must divide c. We have therefore proved:

Equation (1) has a solution if and only if c is a multiple of (a, b).

To determine the other solutions of (1) we observe that if x = x',  y = y' is any solution other than x = x ^*,  y = y^* found above by the Euclidean algorithm, x = x' - x^*,   y = y' - y^* is a solution of the `homogeneous equation'

ax + by = 0.

(3)

For ax'+ by' = c and ax^* + by^* = c, and on subtracting we find that

a(x' - x*) + b(y' - y*) = 0.

Now the general solution of the homogeneous equation (3) is easily seen to be

x =  rb (a, b) ,        y =  -ra (a, b) ,

where r can be any integer. It follows immediately that:

Theorem : The general solution of the linear Diophantine equation (1) is

x = x* +  rb (a, b) ,       y = y* -  ra (a, b) .

where x=x ^*,  y = y^* is any particular solution, found by means of the Euclidean algorithm applied to a, b. This will exist if and only if c is a multiple of (a, b). Let us look at the following examples.

(i)    The equation 3x + 6y = 22 has no solution since (3, 6) = 3 does not divide 22.

(ii)   The equation 7x + 11y = 13 has solution x = -39, y = 26. For

11 = 1·7 + 4,    7 = 1·4 + 3,    4 = 1·3 + 1.

Thus (7, 11) = 1, which divides 13. Further, working from the last equation back to the first,

1 = 4 - 3 = 4 -(7-4) = 2·4 - 7 = 2·11 - 3·7.

Hence

7·(-3) + 11(2) = 1,        7·(-39) + 11(26) = 13.

The other solutions are given by

x = -39 + 11r,        y = 26 - 7r

where r is any integer.

- Munyaradzi Mukachana and Richard Mugero of Victoria High School