오늘 걷지 않으면 내일 뛰어야 합니다

$$유클리드\;호제법의\;확장$$ $$정수\;a\;와\;b\;의\;최대공약수를\;(a,b)\;라고\;하자.$$ $$이\;때,\;아래\;형태의\;해가\;되는\;정수쌍\;x\;와\;y\;를\;구할\;수\;있다.$$ $$ax\;+\;by\;=\;(a,b)$$ $$유클리드\;호제법의\;과정을\;나열하면\;아래와\;같다.$$ $$a\;=\;bq_{1}\;+\;r_{2}$$ $$b\;=\;r_{2}q_{2}\;+\;r_{3}$$ $$r_{2}\;=\;r_{3}q_{3}\;+\;r_{4}$$ $$...$$ $$r_{n-1}\;=\;r_{n}q_{n}\;+\;r_{n+1}$$ $$r_{n}\;=\;r_{n+1}q_{n+1}\;+\;r_{n+2}$$ $$r_{n+1}\;=\;r_{n+2}q_{n+2}\;+\;0$$ $$나머지가\;0..