1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Continued Fractions
  1. Partial fractions (Replies: 8)

  2. Algebraic Fractions (Replies: 3)

  3. Algebraic Fraction (Replies: 11)

  4. Atomic Fractions (Replies: 2)

  5. Multiplying Fractions (Replies: 1)

Loading...