# Homework Help: Continued Fractions

1. Mar 14, 2005

### Zurtex

I'm about to do a test in a couple of days on a course titled "Topics in Pure and Experimental Maths". I was looking over some of the examples we have been given and I have utterly forgotten how to solve Diophantine Equations using Continued Fractions, could some one point me on the right track with this example please:

83x + 259y = 1

2. Mar 14, 2005

### cronxeh

3. Mar 14, 2005

### Zurtex

Thanks but that doesn't really help at all.

4. Mar 14, 2005

### xanthym

Continued fractions can be applied to solve Diophantine Equations of the type:
a*x + b*y = 1
where "a" and "b" are given relatively prime positive integers, and "x" and "y" are required integer solutions.
(Note: Above Diophantine Equation with "1" on the right side has integer solutions only if "a" and "b" are relatively prime. More generally, the Diophantine Equation {a*x + b*y = w} will have integer solutions only if GCD(a,b) divides "w".)
Technique will be illustrated with the following example:
(83)*x + (259)*y = 1

STEP 1: Determine Continued Fraction for {a/b}
Results will be equivalent whether {a/b} or {b/a} continued fraction is determined. However, it's easier when the quotient is greater than 1. Thus, for this example, {259/83} continued fraction will be found. Let the continued fraction coefficients be designated c0, c1, ... , cn. Then it's required to find c's such that:
{259/83} = c0 + 1/c1+1/c2+1/ .... 1/cn-1+1/cn

Coefficients are found using successive quotients involving remainder terms:
{259/83} = 3 + 10/83 -----> c0 = 3
{83/10} = 8 + 3/10 -----> c1 = 8
{10/3} = 3 + 1/3 -----> c2 = 3
{3/1} = 3 -----> c3 = 3
::: ⇒ {259/83} = 3 + (1/(8 + 1/(3 + 1/3)))

STEP 2: Evaluate Continued Fraction Without Final Term
Continued fraction's last term is dropped, and the new FRACTION it represents is determined:
{259/83} = 3 + (1/(8 + 1/(3 + 1/3)))
3 + (1/(8 + 1/(3 + 0))) = {78/25}

STEP 3: Cross-Multiply And Determine Sign
{259/83} ~ {78/25}:
(259)*(25) = (6475)
(78)*(83) = (6474)
Thus, x=(-78) and y=(25):
(83)*(-78) + (259)*(25) = 1

~~

Last edited: Mar 14, 2005