Recognitions:
Homework Help

## Continued Fractions

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
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
 Recognitions: Gold Member Your best bet is this: http://mathworld.wolfram.com/DiophantineEquation.html also has a page on continued fractions http://mathworld.wolfram.com/ContinuedFraction.html
 Recognitions: Homework Help Science Advisor Thanks but that doesn't really help at all.

Recognitions:

## Continued Fractions

 Quote by 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
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

~~

 Similar discussions for: Continued Fractions Thread Forum Replies Calculus & Beyond Homework 1 Linear & Abstract Algebra 1 Precalculus Mathematics Homework 3 Precalculus Mathematics Homework 13 Linear & Abstract Algebra 4