Section 2.1
Problem 2:
Solution:
First we find the greatest common divisor of 1819 and 3587 using euclidean algorithm
3587 = 1819 (1) + 1768
1819 = 1768 (1) + 51
1768 = 51 (34) + 34
51 = 34 (1) + 17
34 = 17 (2) + 0
=> greatest common divisor of 1819 and 3587 is 17
Now we find the values of x and y from 1819 x + 3587 y = g.
choose x = 0 and y = 1
1819 (0) + 3587 (1) = 3587 → equation 1.
choose x = 1 and y = 0
1819 (1) + 3587 (0) = 1819 → equation 2
multiply with the first quotient from the steps of euclidean algorithm to equation 2 and subtract it from equation 1. r_0 = 1
1819 (-1) + 3587 (1) = 1768 → equation 3
multiply r_1 = 1 to equation 3 and subract it from equation 2
1819 (2) + 3587 (-1) = 51 → equation 4
multiply r_2 = 34 to equation 4 and subract it from equation 3
1819 (-69) + 3587 (35) = 34 → equation 5
multiply r_3 = 1 to equation 5 and subract it from equation 4
1819 (71) + 3587 (-36) = 17
=> x = 71 and y = -36.