##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Backtracking through steps
Run normal Euclidean algorithm and record all the steps. Then backtrack, expressing each remainder as a linear combination of a and b.
Example: gcd(12, 18). Step 1: 18 = 12 × 1 + 6. Step 2: 12 = 6 × 2 + 0. Backtrack: 6 = 18 - 12 × 1. So x = -1, y = 1.
The algorithm builds the coefficients recursively. I will not go deeper here, but know this tool exists.
