Good stuff Gaines! To clarify your procedure for others who may be interested, here's how I think about this. For the sake of argument, if the coefficients were small enough, say 2 and 5 (instead of 41 and 107), then the problem would be 2a + 5b = 1 and we could easily see that a=-2 and b=1 would satisfy the equation. So the trick should be to reduce the coefficients and get them small enough until the answer jumps out at you. This is done as follows:
We have:
(1): 41a + 107b = 1
Step 1: write 107 = 2*41 + 25 and substitute in (1) to obtain:
(2): 41(a+2b) + 25b = 1 note that the coefficients reduced from (41, 107) to (41, 25)
Step 2: write 41 = 25 + 16 and substitute in (2) to obtain:
(3): 16(a+2b) + 25(a+3b)=1 note that the coefficients further reduced from (41, 25) to (16, 25)
Step 3: write 25 = 16 + 9 and substitute in (3) to obtain:
(4): 16(2a+5b) + 9(a+3b)=1
Step 4: write 16 = 9 + 7 and substitute in (4) to obtain:
(5): 7(2a+5b) + 9(3a+8b)=1
Step 6: write 9 = 7 + 2 and substitute in (5) to obtain:
(6): 7(5a+13b) + 2(3a+8b)=1
At this stage, it is easy to see that:
5a + 13b = 1
3a + 8b = -3
would give us the solution (thanks to the small coefficients 7, 2) Finally, we can solve the two equations for a an b to obtain:
a = 47
b = -18
By the way, I believe the "old dude" that you refer to who came up with this algorithm was Euclid from 300 B.C. (LOL)
We have:
(1): 41a + 107b = 1
Step 1: write 107 = 2*41 + 25 and substitute in (1) to obtain:
(2): 41(a+2b) + 25b = 1 note that the coefficients reduced from (41, 107) to (41, 25)
Step 2: write 41 = 25 + 16 and substitute in (2) to obtain:
(3): 16(a+2b) + 25(a+3b)=1 note that the coefficients further reduced from (41, 25) to (16, 25)
Step 3: write 25 = 16 + 9 and substitute in (3) to obtain:
(4): 16(2a+5b) + 9(a+3b)=1
Step 4: write 16 = 9 + 7 and substitute in (4) to obtain:
(5): 7(2a+5b) + 9(3a+8b)=1
Step 6: write 9 = 7 + 2 and substitute in (5) to obtain:
(6): 7(5a+13b) + 2(3a+8b)=1
At this stage, it is easy to see that:
5a + 13b = 1
3a + 8b = -3
would give us the solution (thanks to the small coefficients 7, 2) Finally, we can solve the two equations for a an b to obtain:
a = 47
b = -18
By the way, I believe the "old dude" that you refer to who came up with this algorithm was Euclid from 300 B.C. (LOL)
