Euclid's Algorithm: >>> euc(132,105) 132=105Q+27 105=27Q+24 27=24Q+3 3 So 3= gcd(132,105) To solve 132x+105y = 33 ..... (1) Carlson's Algorithm: >>> isolve(132,105,33) [44, -55] is Python's answer. Just checking, >>> 132*44 -105*55 33 So we believe this solution to the DE Now we do it by hand. 132x + 105y = 33 the target DE 132 = 105(1) + 27 by long division (105(1) + 27)x + 105y = 33 by substitution 105((1)x + y) + 27(x) = 33 by rearrangement For [u,v]:= [x+y, x] or [x,y]=[v,u-v] we get a 105u + 27v = 33 second DE 105=27(3)+24 by long division (27(3)+24)u + 27v = 33 by substitution 27(3u +v) + 24u = 33 by rearrangement For [m,n]:=[3u+v, u] or [u,v]=[n,n-3m] we get a 27m + 24n = 33 third DE 27 = 24(1) + 3 by long division (24(1)+3)m + 24n = 33 by substitution 24( (1)m +n ) + 3(m) = 33 by rearrangement For [h,k]=[m+n, m] or [m,n]=[k,h-k] we get a 24h + 3k = 33 fourth DE 24 = 3(8) + 0 by long division So [h,k] = [0, 33/3= 11] solves the 4thDE so [m,n] = [k,h-k] = [11, -11] solves 3rdDE So [u,v] = [n,n-3m]= [-11, 44] solves 2ndDE So [x,y] = [v,u-v] = [44, -55] solves the DE Which is the answer the isolve algorithm also returns.