Recall the set of four problems from the blog on the Euclidean algorithm and Diophantine equations:
1) Carry out the Euclidean algorithm for finding the greatest common divisor of (187, 77)
2) Reduce (245, 193) via the Euclidean Algortihm:
3) Using the Euclidean Algorithm show the continued fraction for: (237/ 139)
4) Solve the Diophantine equation: 3x - 4y = 29
Solutions:
1) We have (a,b) = (187, 77)
Take: (187)/ 77 = 2 R33 [e.g. 187 – 154]
= 2*77 + 33 or (77, 33)
So take: (77)/ 33 = 2 R11 [e.g. 77 – 66 = 11]
= 2*33 + 11 = (33, 11) = 3*11 + 0
Hence: (187, 77) = (33,11)
2) We have (a,b) = (245, 193)
=> (245) / 193 = 1 R52 [e.g. 245 – 193 = 52]
= 1*193 + 52 = (193, 52)
=> (193)/ 52 = 3 R 37 [e.g. 193 – 156 = 33]
= 3*52 + 37 = (52, 37)
But: (52, 37) = (52)/ 37 = 1 R 15 [e.g. 52 – 37 = 15]
= 1*37 + 15 = (37, 15)
But (37, 15) => (37)/ 15 = 2 R 1 = 2*7 + 1
= (7, 1) and 7/1 = 7
Hence: (245, 193) = (193, 52) = (52, 37) = (37, 15) = (15, 7) = (7, 1)
3) Take 237/ 139 = 1 + 98/139 = 1 + 1/ (139/98)
139/98 = 1 + 41/98 = 1 + 1/ (98/41)
98/41 = 2 + 16/41 = 2 + 1/ (41/16)
But: 41/ 16 = 2 + 9/16
This will then be laid out in continued fraction form such that the final form will be analogous to that shown in the images for the blog, but with 2 + 9/16 in the final denominator.
4) Solve: 3x - 4y = 29
There are no immediate integral solutions since neither 3 or 4 divide evenly into 29. So we write:
4 = 1*3 + 1 and 3 + 1*2 + 1 and 1 = 4- 3 so that (3, 4) = 1
=> 3(3) - 4(2) = 1
=> 3(11) - 4(1) = 29
So that x = 11, and y = 1
Other solutions (for r = integer) can be obtained using:
x = 11 + 4r and y = 1 + 3r
Check for r =2 : x = 11 + 4(2) = 19 and y = 1 + 3(2) = 7 = 7
Subst. into the equation: 3x - 4y = 29 to get: 3(19) - 4(7) = 57 - 28 = 29
Other values of r can also be tried by the reader, just ensure they're integers!
No comments:
Post a Comment