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.