| Thread Closed |
Continued Fractions |
Share Thread |
| Mar14-05, 08:38 AM | #1 |
|
Recognitions:
|
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 |
| Mar14-05, 09:07 AM | #2 |
|
|
Your best bet is this: http://mathworld.wolfram.com/DiophantineEquation.html
also has a page on continued fractions http://mathworld.wolfram.com/ContinuedFraction.html |
| Mar14-05, 01:12 PM | #3 |
|
Recognitions:
|
Thanks but that doesn't really help at all.
|
| Mar14-05, 09:02 PM | #4 |
|
Recognitions:
|
Continued Fractionsa*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 ~~ |
| Thread Closed |
Similar discussions for: Continued Fractions
|
||||
| Thread | Forum | Replies | ||
| Continued Fractions. | Calculus & Beyond Homework | 1 | ||
| continued fractions | Linear & Abstract Algebra | 1 | ||
| Continued Fractions | Precalculus Mathematics Homework | 3 | ||
| continued fractions | Precalculus Mathematics Homework | 13 | ||
| continued fractions | Linear & Abstract Algebra | 4 | ||