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.
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 ].
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
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)\)
