# 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)$$