Math Revisited: Continued Fractions And Diophantine Equations

An area of ongoing interest, historical and otherwise, is that pertaining to Diophantine Equations, which includes the use of continued fractions (see image) and the Euclidean algorithm. The latter is especially useful for solving Diophantine equations, as well as generating continued fractions such as those shown. Continued fractions, for their part, are key aspects of a branch of higher arithmetic known as 'Diophantine analysis'.

A Diophantine equation "is an algebraic equation in one or more unknowns, with integer coefficients, for which integer solutions are sought", according to the authors of 'What is Mathematics?'.  They add that such an equation may "have no solutions, a finite number of solutions or an infinite number." As the simplest example of such an equation they give: ax + by = c.

Here, a, b and c denote integers and the equation needs to be solved for x and y, and ideally these solutions are integers, not fractions.  At this point, we have to cut to the Euclidean algorithm and how it's used.  A general theorem may be stated thus: If a is any integer, and b is any integer greater than zero, then we can always find an integer q such that:

a = b*q + r

where r is an integer satisfying the inequality:  0 < r < b

A general task is to find the “greatest common divisor” (gcd)  of a and b, called d(a,b). If d = (a,b)then positive or negative integers k and m can always be found such that:  d = ka + mb

This proceeds by successive divisions with remainders. As an example, consider the Euclidean algorithm for finding (a,b) = (61, 24). Here gcd or greatest common divisor is 1 and we find:


61 = 2*24 + 13

24 = 1*13 + 11

13 = 1*11 + 2

11 = 5*2 + 1

2 = 2*1 + 0

From the 1st equation we have: 13 = 61 - 2*24

From the end of the second result we get:


11 = 24 – 13 = 24 - 61 - 2*24 = -61 + 3*24

From the third:


2 = 13 – 11 = (61 – 2*24) – (-61 + 3*24) = 2*61 – 5*24


From the fourth:

1 = 11 – 5*2 = (-61 + 3*24) – 5(2*61 – 5*24) = -11.61 + 28*2

Apart from these operations, we can also use the Euclidean algorithm to compute continued fractions. Examples are shown in Fig. 1. Now, let’s look more closely at continued fractions. We see in Fig, 1 how 2/5 is converted into a continued fraction.

We look, for example,  at 169/70 and seek the continued fraction development:

169/70 = 2 + 29/70 = 2 + 1/70/29

 70/29 = 2 + 12/29 = 2 + 1/ (29/12)


29/12 = 2 + 5/18 = 2 + 1/ (12/5)


12/5 = 2 + 2/5 = 2 + 1/(5/2)

And: 5/2 = 2 ½ = 2 + ½


Thus 169/70 is developed as shown (Fig. 1) with result = 2.414

Let's now see how the preceding operations can be used to solve a Diophantine equation. In particular, we want to solve: 7x + 11y = 13   We proceed by working with 7 and 11, respectively, using the Euclidean algorithm.

Thus:   11 = 1*7 + 4  and 7 = 1*4 + 3  

We see remainder 4 for the first, so use the algorithm again, so: 4 = 1*3 + 1

 Then we can write: (7, 11) = 1  

Meanwhile, the remainder of 1 (after working on remainder 4) is dealt with, so: 

  1 = 4 - 3 = 4 - (7 - 4) = 2*4 - 7 = 2 (11 - 7) - 7 =  2*11 - 3*7

 Therefore:   7*(-3) + 11(2) = 1   and   7*(-39) + 11(26) = 13
 From the last equation we see that x = -39 and y = 26.

All other solutions can be expressed in terms of x and y -values with a remainder r (integer), so that:  
x = -39 + 11r  and y = 26 - 7r  

For example, let r = 1, then x = (-39) + 11 = - 28 is also a solution.  Similarly, let r = 1 and y = 26 -7
(1) = 26 - 7 = 19 is also a solution.  

In summary then, the linear Diophantine equation of form ax + by = c has a solution in integers if and only if c is a multiple of (a, b). In this case, a particular solution may be found using the Euclidean algorithm.  


Problems for the Math Maven:
1) Carry out the Euclidean algorithm for finding the greatest common divisor of (187, 77)

2) Reduce (245, 193) via the Euclidean Algortihm:

3) Using the Euclidean Algorithm show the continued fraction for:  (237/ 139)

4) Solve the Diophantine equation: 3x - 4y = 29