Continued Fractions

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

cronxeh

Your best bet is this: http://mathworld.wolfram.com/DiophantineEquation.html
also has a page on continued fractions http://mathworld.wolfram.com/ContinuedFraction.html

Zurtex

Thanks but that doesn't really help at all.

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 c₀, c₁, ... , c_n. Then it's required to find c's such that:
{259/83} = c₀ + 1/c₁+1/c₂+1/ .... 1/c_n-1+1/c_n

Coefficients are found using successive quotients involving remainder terms:
{259/83} = 3 + 10/83 -----> c₀ = 3
{83/10} = 8 + 3/10 -----> c₁ = 8
{10/3} = 3 + 1/3 -----> c₂ = 3
{3/1} = 3 -----> c₃ = 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


~~