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.