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