Solutions to Math Problems

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!