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:
which incidently shows that the greatest common divisor (840, 611) = 1.
From these equations, we
have derived the following expressions:
Combining these operations, we obtain the development of the rational
number [ 840/611] in the form
An expression of the form
a = a_{0} + 
1
a_{1} + 
1
a_{2} + 
1
:+ [ 1/(a_{n1} + [ 1/(a_{n})])]





where the a's are positive integers, is called a continued
fraction. There are also nonterminating 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:
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
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):
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'
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 (74) = 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
T_{E}X
by
T_{T}H,
version 3.01.
On 23 Jul 2002, 13:26.