>ただこれは何故こんなややこしいことをするのかは
>多分、結論から逆に辿った感があり、説明出来ないと思う

これが拡張ユークリッドの互除法のアルゴリズムだから。