Diophantine Equation

Introduction

In mathematics, a Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations. In more technical language, they define an algebraic curve, algebraic surface or more general object, and ask about the lattice points on it.

While individual equations present a kind of puzzle and have been considered throughout history, the formulation of general theories of Diophantine equations (beyond the theory of quadratic forms) was an achievement of the twentieth century.

Linear Diophantine equations take the form ax + by = c. If c is the greatest common divisor of a and b then this is Bézout's identity, and the equation has infinitely many solutions. These can be found by applying the extended Euclidean algorithm. It follows that there are also infinitely many solutions if c is a multiple of the greatest common divisor of a and b. If c is not a multiple of the greatest common divisor of a and b, then the Diophantine equation ax + by = c has no solutions.

Conditions for Diophantine equation to have solution.
i. The greatest common divisor of a and b divide c.
ii. No three of a,b,c,d have a common factor 1.
iii. Intergers (x,y) is a solution of the linear Diophantine equation ax+by=c if and only if the (x,y) is a lattice point in the plane that lies in line ax+by=c.

Method to find the solution of ax+by=c .

i. Given an equation of ax+by=c. First,find the greatest common divisor of a and b using Euclidean algorithm.

Example : Determine all solution in intergers of
24x+138y=18
The computation is as follows :
138 = 5•24 + 18
24 = 1•18 + 6
18 = 3•6 + 0
So,the gcd(24,138)=d=6.

ii. Check whether gdc(a,b) divide c or not. With regards to example above,since 618,hence the equation 24x+138y=18 has a solution.


iii. Obtain c in linear combination of a and b.

To obtain 6 in linear combination of 24 and 138,we work backward through the previous computation as follows :
138 = 5•24 + 18 18 = 138 - 5•4
24 = 1•18 + 6 6 = 24 - 1•18
18 = 3•6 + 0

6 = 24 - 1•18
= 24 – 1 (138 - 5•4)
= 24 - 1•138 + 5•4
= 6•24 - 1•138
= 6•24 + (-1)•138
Hence,6 in linear combination of 24 and 138 is 6= 6•24 + (-1)•138.

iv. Continuing from example above,upon multiplying the 6= 6•24 + (-1)•138 by 3,we obtain
18 = 18•24 + (-3)•138
Thus, and .

Other solution are obtained by using formulae and

The other solution are given by x = 18 + 23t and y = -3 – 4t for .....and so on.