What is a continued fraction?

A finite continued fraction (FCF) is an expression of the form:

where a0, a1, ..., an are real numbers, all of which except possibly a0 are positive. Such a fraction is called simple if all the ai are integers. The expression is denoted as [a0; a1, . . . , an].

Any rational number can be expressed as a FCF. Recall that the reciprocal of a number is simply obtained by dividing 1 by that number. Consider the fraction 45/16, using reciprocals, this fraction can be written as: 

Hence we obtain 45/16 = [2; 1, 4, 3].

Euclid's Algorithm is well known for finding the highest common factor between two integers, where we repeatedly employ division by remainder. The procedure is as follows: given two natural numbers a, b with a > b > 0, we can write

a= q1b+r1     where b >r1 ≥ 0 

b= q2r1+r2    where r1 > r2 ≥ 0 

r1= q3r2+r3   where r2 > r1 ≥ 0

in general rt = qt+2rt+1 + rt+2 with rt+1 > rt+2 ≥ 0.

When the procedure stops, which it will, then there exists k such that                             rk−1 = qk+1rk + rk+1 and rk = qk+2rk+1 + 0.                                                    

Then rk+1 is the highest common factor of a and b.

Now Euclid's Algorithm can be used to compute the continued fraction expression of a number, which I think is more straightforward than the reciprocal procedure, especially in terms of display. Let's reconsider the fraction 45/16:

45 = 2 x 16 + 13                                                                                         

16 = 1 x 13 + 3                                                                                            

13 = 4 x 3 + 1                                                                                               

13 = 3 x 1 + 0

Now it's easy to see that the quotients we get each time is an entry in the continued fraction expression.

Convergents

One of the reasons why we consider the continued fraction expression of a number is to approximate the number, for example, it can be shown that every irrational number has an infinite continued fraction expression. Here is where the idea of convergent comes in: for 0 ≤ k ≤ n, [a0; a1, . . . , ak] is called the kth convergent to the given continued fraction [a0; a1, . . . , an]. We denote it by Ck. Thus for 45/16, C0 = 2, C1 = [2; 1], C2 = [2; 1, 4], C3 = [2; 1, 4, 3]. 

Recall that I said earlier every rational number has a FCF expression, and it's also true the other way round: every FCF is a rational number. Thus we may ask the question: since convergents are FCF, what rational number do they represent? The answer is given by the following sequences where we define them recursively: 

(1) p−1 = 1, p0 = a0 and pn = anpn−1 + pn−2, 

(2) q−1 = 0, q0 = 1 and qn = anqn−1 + qn−2. 

And you can use induction to show that pk/qk = [a0; a1, . . . , ak] = Ck

Solutions to Linear Diophantine Equations

Linear Diophantine equations model many real-world problems, including resource allocation, scheduling, and balancing problems where solutions must integers. They also play a critical role in cryptography, particularly in algorithms like the RSA algorithm. Understanding these equations is essential for developing and analysing secure cryptographic systems.

A linear Diophantine equation is of the form ax+by = c, where a, b and c are integers, a and b both non-zero. This solution has an integer solution (x,y) if and only if hcf(a,b) divides c, in other words, it's a factor of c. For now, we only consider equations where c = ±1, where we can find a solution for the linear Diophantine equation quite easily. If c does not equal ±1, we can still start by working with the equation where c = ±1, according to the sign of c, when we have obtained one particular solution (x,y), we can multiply them by c and get a particular solution.

First let's note a pattern that the convergents possess: if Ck = pk/qk is the kth convergent of [a0; a1, . . . , an], then pkqk−1 − qkpk−1 = (−1)k−1.

Here is an example with some pretty nasty numbers: 843371x + 379525y = -1, the convergents for 843371/379525 are in the following table:

Using the above pattern when k = 10, we get p10q9 − q10p9 = 843371(70719) + 379525(-157150) = 1.

Hence a particular solution is (70719, -157150).

However, most of the time the particular solution that we obtain are not the one we want. For example, if you are trying to calculate how many people (adults and children) went to a concert, a negative number does not make sense at all. But do not worry, as long as you have one particular solution, we can work out the general solution then you can pick one that you think is the most sensible!

If (x0,y0) is a particular solution, then the general solutions are given by

where d = hcf (a, b).