Diophantine Equations

Test the equation Ax - By = C -->  -
Parent Form (linear) Ax - By = C     ---->         x -y =  
 y (if diophantine equation ) shall be between 1 and (integer only)
1st reduction A1x1 - B1y1 = C1    --->   x1 -y1
ymin =

xmin =

x1 y1 x =  y = 
2nd reduction A2x2 - B2y2 = C2 --->    x2 -y2
  x2

x1

y2

y1

x =  y = 
3rd reduction A3x3 - B3y3 = C3 --->    x3 -y3
  x3

x2

x1

y3

y2

y1

x =  y = 
4th reduction A4x4 - B4y4 = C4 --->    x4 -y4
  When C= ,  y =, then when C =  ,y= or 
LCM:       GCD: (between A and B)
 

 

Diophantus, often called the father of Algebra, was a 3rd Century Greek mathematician( he lived around 250A.D) who is credited for writing one of the first books on algebra  "Arithmetica" and was one of the first mathematicians to recognize fractions as positive integers. Very little about his life is known than that what was written down on his tombstone:

God granted him to be a boy for the sixth part of his life,
and adding a twelfth part to this, He clothed his cheeks with down.
He lit him the light of wedlock after a seventh part,
and ve years after his marriage He granted him a son.
Alas! late-born wretched child; after attaining
the measure of half his father's life, chill Fate took him.
After consoling his grief by this science of numbers
for four years he ended his life.

How old was Diophantus when he died? This riddle is an example for the kind of problems in which Diophantus was interested in.

Diophantine equations are indeterminate polynomial equations in which only integer solutions are allowed. (1)For a 1st order Diophantine equation, there is an algorithm to determine whether there exists a solution. A linear Diophantine equation of 2 variables is of the form Ax + By = C where A, B and C are integers. The first known solution was furnished by Brahmagupta.

(2)Fibonacci numbers have a diophantine representation. A pair of consecutive fibonacci numbers do indeed satisfy the equation: x2+xy-y2 = ±1 and the solutions (x, y) in positive integers to the equation (x2+xy-y2)2 - 1= 0 are the pairs of consecutive Fibonacci numbers.

(3) The linear Diophantine equation ax-by=c with integers a, b, c is solvable if and only if gcd of a and b divides c OR   (b, a) |c. Example- take 38x-15y=1. Various solutions (x, y) are (-13,-33),(2,5),(17,43). solutions yield good approximations to 15/38 i.e. (x/y) --> 15/38.One can work out on other equn. 3x-5y=19, 117x-125y=91 etc. If the linear Diophantine equation is solvable, there are infinite number of integer solutions.

(4) Euclid showed that if there exist 2 integers a, b , then gcd (a, b) can be expressed as a linear combination of a and b. Or ax + by = gcd (a, b)

Some Observations

(1) If Ax -By=C is a Diophantine equation, and a solution is found out at x=m, y=n,

then (m+ B, n+ A),(m+2B,n+2A),(m+3B,n+3A,...(m+ kB, n+ kA) are also solutions where k is an integer (positive or negative).

(2) If Ax -By=C is a diophantine equation & the lowest difference between x, y   i.e.       x-y =Δ , then in general x-y = Δ +k (B-A) where k is an integer.

(3)      If Ax -By=C is a  Diophantine equation & the lowest sum between x, y  i.e.  x+ y =δ , then in general x+ y =δ + k (B+ A) where k is an integer, positive or negative.

(4)  If Ax -By = C is a  Diophantine equation, no. of lowest values that y can take is A irrespective of the value of C and B. For example, if 2x-5y=C, the lowest value of y can be 1 or 2--> only these 2 values whether C is 1,2,3,4,17 etc and /or B is of any value. Again , if 3x-5y=C, lowest y can take only any of the 3 values (1,2 or 3). If 6x-5y=C, y shall take any of 6 values (1,2,3,4,5,6) irrespective of value of B, C.

(5) If Ax -By = C is a  Diophantine equation where y= m, then y = m for the equation Ax -By = C ± kA where k is an integer. Example -- In the equation, 15x-7y =4 , y=8 (lowest value). Then y = 8 (lowest value) also for the equation 15x-7y =19 and 15x-7y=34 etc.

(6) If Ax -By = C is a  Diophantine equation for which lowest value of y is m, then for Ax-(B+kA)y = C, y=m where k is an integer.

(7) If Ax-By = C is a diophantine equation &  lowest value of y is  m, then for kAx-kBy=kC, lowest value of y shall also be m where k is an integer.

(8) If Ax-By = C is a diophantine equation &  lowest value of y is  m and Ax-B1y = C,Ax-B2y = C,Ax-B3y = C etc upto Ax-(A-1)y = C are various diophantine equations where B=1,B1=2,B2=3 etc and lowest value of y are m1,m2,m3,m4 etc , then for a specific value of  Bm, if there exist any combination of products with same value,then these are also values of some B and m provided m<=A.

Example:-39x- y =3 where lowest value of y i.e m=36. So here Bm= 36. Other combination with product 36 are (18,2) , (9,4),(6,6),(4,9),(2,18),(36,1).Hence other diophantine equations are

39x-18y= 3 Lowest value of y= 2  (18,2)

39x-9y = 3 Lowest value of y=  4  (9,4)

39x-6y= 3 Lowest value of y = 6  (6,6)

39x-4y= 3 Lowest value of y = 9  (4,9)

39x-2y= 3 Lowest value of y = 18  (6,6)

39x-36y= 3 Lowest value of y = 1  (36,1)

Here all Bm are 36.

In the same way if 39x-5y=3 & lowest value of y is 15 then Bm is 75 (5,15).Other combinations are (3,25),(25,3),(15,5). Corresponding diophantine equations are

39x-3y= 3  value of y= 25  (3,25)

39x-25y= 3  value of y= 3  (25,3)

39x-15y= 3  value of y= 5  (15,5)

All are acceptable values of y as these are <=39. (75,1) is also an option but not acceptable as B=75 which is greater than 39.

(9) In the above case where A,C remain constant and B changes leading to various values of y,the various values of Bm are lowest value of Bm +kA where k is an integer.In example above, since lowest value of Bm is 36, other values are 75,114,153,192,231,270,309 .....1050.(Some values are excluded such as 543 as it is (3,181) and (181,3) out of which 181 value of y is not the lowest value and 181 value of B is greater than A. However, they correspond to a pair of values of B,y which form diophantine equations) One can take their product combinations and construct diophantine equations with value of y. Example-- If we take 270, the combinations are (135,2),(2,135)(45,6),(6,45),(15,18)(18.15),27,10), (10,27).Excluding the red colored combinations which are not lowest value of y, other form the equation such as 39x-15y=3 where y=18 and so on so forth.

Solution of Diaphantine Equn of type Ax2 +Bxy+cy2+Dx+Ey+F=0, click     NEXT