# Applications of Continued fractions

Continued fraction concept is very useful in solving linear equations $ax - by = \pm c$ in integers.
We know that rational numbers are in the format of $\dfrac{p}{q}$ where $q \ne 0$.  For example, $\dfrac{{42}}{{29}}$.
If we represent $\dfrac{{42}}{{29}}$ in a continued fraction, then, $\cfrac{{42}}{{29}} = 1 + \cfrac{1}{{2 + \cfrac{1}{{4 + \cfrac{1}{3}}}}}$
Or concisely, $\dfrac{{42}}{{29}}$ = $[1;~2,~4,~3]$
(Don't worry about how I have written the above expression!! This can be done easily by Euler's division algorithm which is explained below)
By representing a fraction in this format, we can find convergents.  We know that, $\dfrac{{42}}{{29}}$ = 1.44827586207
The first convergent of $\dfrac{{42}}{{29}}$ = $1$
Second convergent = $1 + \dfrac{1}{2}$ = $\dfrac{3}{2}$
Third convergent = $1 + \cfrac{1}{{2 + \cfrac{1}{4}}}$ = $\dfrac{{13}}{9}$
Fourth convergent = $\cfrac{{42}}{{29}} = 1 + \cfrac{1}{{2 + \cfrac{1}{{4 + \cfrac{1}{3}}}}}$ = $\dfrac{{42}}{{29}}$

Convergents are approximations of the given number.
First convergent = 1; Second convergent = 1.5; Third convergent = 1.4444444;
You can see that the values are slowly converging towards 1.448275....

But how do we convert a number in continued fraction format. This is very simple.  If you find HCF of 42 and 29 by using division method, the quotients are [1, 2, 4, 3 ]. Therefore continued fraction = $\dfrac{p}{q} = {a_1} + \cfrac{1}{{{a_2} + \cfrac{1}{{{a_3} + \cfrac{1}{{{a_4} + ...}}}}}}$
Here ${a_1},~{a_2},~{a_3},~{a_{4,}}...$ are quotients.

### Applications of continued fractions:

Question 1:
Find the general solution in positive integers of $29x - 42y = 5$
Solution:
To find the general solution in positive integers of the equation $ax - by = c$ we can use continued fractions.
Let $\dfrac{a}{b}$ is converted into a continued fraction, and Let $\dfrac{p}{q}$ denote the last but one convergent, then $aq - bp = \pm 1$
We have to find the general solution in positive integers of $29x - 42y = 5$
From the above discussion, the convergent just  before $\dfrac{{42}}{{29}}$ is $\dfrac{{13}}{9}$.
Therefore, $29 \times 13 - 42 \times 9 = - 1$
Multiplying the above equation with $5$, we get
$\therefore 29 \times 65 - 42 \times 45 = - 5$
$\therefore 42 \times 45 - 29 \times 65 = 5$
Equating the above equation with the given question,
$29x - 42y = 42 \times 45 - 29 \times 65$
$29\left( {x + 65} \right) = 42\left( {y + 45} \right)$
$\dfrac{{\left( {x + 65} \right)}}{{42}} = \dfrac{{\left( {y + 45} \right)}}{{29}}$
Let $\dfrac{{\left( {x + 65} \right)}}{{42}} = \dfrac{{\left( {y + 45} \right)}}{{29}} = t$
So general solution is, $x = 42t - 65$; $y = 29t - 45$

Question 2:
Find the general solution in positive integers of $775x - 711y = 1$
Solution:
Converting $\frac{{775}}{{711}}$ in continued fractions, we get So $\cfrac{{775}}{{711}} = 1 + \cfrac{1}{{11 + \cfrac{1}{{9 + \cfrac{1}{7}}}}}$
Last but one convergent of = $\dfrac{{775}}{{711}}$ = $1 + \cfrac{1}{{11 + \cfrac{1}{9}}}$ = $\dfrac{{109}}{{100}}$
Therefore, $775 \times 100 - 711 \times 109 = 1$
Equating with the given question,
$775 \times 100 - 711 \times 109 = 775x - 711y$
$775 \times \left( {x - 100} \right) = 711 \times \left( {y - 109} \right)$
$\dfrac{{\left( {x - 100} \right)}}{{711}} = \dfrac{{\left( {y - 109} \right)}}{{775}}$ = $t$ say
So $x = 711t + 100$; $y = 775t + 109$
For $t = 0$, we get the first solution $(100, 109)$