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

Follow: |
Share: |