## Number Theory: Diophantine Equations

### Introduction

Integers have gradually lost association with superstition and mysticism, but their interest for mathematicians has never waned. Among the greatest mathematicians is Diophantus of Alexandria (275 A D), an early algebraist, sometimes called `The Father of Algebra'. He left his mark on the theory of numbers, and his name - there are Diophantine numbers, and Diophantine equations.

### Diophantine Equations

The Euclidean algorithm for finding the greatest common divisor of two integers leads to an important method for representing the quotient of two integers as a composite fraction. For example, applied to 840 and 611, the Euclidean algorithm yields the series of equations:
 840
 =
 1 · 661 + 229
 611
 =
 2 · 229 + 153
 229
 =
 1 · 153 + 76
 153
 =
 2 · 76 + 1
which incidently shows that the greatest common divisor (840, 611) = 1.

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

File translated from TEX by TTH, version 3.01.
On 23 Jul 2002, 13:26.