Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Continued Fractions

  1. Mar 14, 2005 #1

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    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. jcsd
  3. Mar 14, 2005 #2

    cronxeh

    User Avatar
    Gold Member

  4. Mar 14, 2005 #3

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Thanks but that doesn't really help at all.
     
  5. Mar 14, 2005 #4

    xanthym

    User Avatar
    Science Advisor

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook