유클리드 호제법의 확장

$$유클리드\;호제법의\;확장$$

$$정수\;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이\;되는\;순간까지\;반복한다.$$

$$이\;때,\;r_{n+2}\;=\;(a,b)\;가\;된다.$$

$$r_{n}\;=\;r_{n+1}q_{n+1}\;+\;r_{n+2}$$

$$\Rightarrow\;r_{n}\;=\;r_{n+1}q_{n+1}\;+\;(a,b)$$

$$\Rightarrow\;r_{n}\;-\;r_{n+1}q_{n+1}\;=\;(a,b)$$

$$r_{n}\;-\;r_{n+1}q_{n+1}\;\Rightarrow\;ax\;+\;by\;의\;형태로\;정리할\;수\;있다면$$

$$ax\;+\;by\;=\;(a,b)\;의\;해가\;되는\;x\;와\;y\;의\;쌍을\;구할\;수\;있다.$$

$$첫번째\;식을\;살펴보자.$$

$$a\;=\;bq_{1}\;+\;r_{2}$$

$$\Rightarrow\;a\;-\;bq_{1}\;=\;r_{2}$$

$$\Rightarrow\;a\;+\;b(-q_{1})\;=\;r_{2}$$

$$ax_{2}\;+\;by_{2}\;=\;r_{2}\;의\;해를\;구한다면,\;아래와\;같다.$$

$$x_{2}\;=\;1,\;y_{2}\;=\;-q_{1}$$

$$두번째\;식을\;살펴보자.$$

$$b\;=\;r_{2}q_{2}\;+\;r_{3}$$

$$\Rightarrow\;b\;-\;r_{2}q_{2}\;=\;r_{3}$$

$$\Rightarrow\;b\;-\;(a\;-\;bq_{1})q_{2}\;=\;r_{3}$$

$$\Rightarrow\;b\;-\;aq_{2}\;+\;bq_{1}q_{2}\;=\;r_{3}$$

$$\Rightarrow\;a(-q_{2})\;+\;b(1+q_{1}q_{2})\;=\;r_{3}$$

$$ax_{3}\;+\;by_{3}\;=\;r_{3}\;의\;해를\;구한다면,\;아래와\;같다.$$

$$x_{3}\;=\;-q_{2},\;y_{3}\;=\;1+q_{1}q_{2}$$

$$세번째\;식을\;살펴보자.$$

$$첫번째\;식과\;두번째\;식을\;대입하면\;아래와\;같다$$

$$r_{2}\;=\;r_{3}q_{3}\;+\;r_{4}$$

$$\Rightarrow\;r_{2}\;-\;r_{3}q_{3}\;=\;r_{4}$$

$$\Rightarrow\;(a\;+\;b(-q_{1}))\;-\;(a(-q_{2})\;+\;b(1+q_{1}q_{2}))q_{3}\;=\;r_{4}$$

$$x2,\;y2,\;x3,\;y3\;로\;표현하면\;규칙을\;찾을\;수\;있다.$$

$$\Rightarrow\;(ax_{2}\;+\;by_{2})\;-\;(ax_{3}\;+\;by_{3})q_{3}\;=\;r_{4}$$

$$\Rightarrow\;a(x_{2}\;-\;x_{3}q_{3})\;+\;b(y_{2}\;-\;y_{3}q_{3})\;=\;r_{4}$$

$$ax_{4}\;+\;by_{4}\;=\;r_{4}\;의\;해를\;구한다면,\;아래와\;같다.$$

$$x_{4}\;=\;x_{2}\;-\;x_{3}q_{3},\;y_{4}\;=\;y_{2}\;-\;y_{3}q_{3}$$

$$아래\;점화식들을\;도출할\;수\;있다.$$

$$x_{n}\;=\;x_{n-2}\;-\;x_{n-1}q_{n-1}$$

$$y_{n}\;=\;y_{n-2}\;-\;y_{n-1}q_{n-1}$$

$$점화식을\;적용한\;유클리드의\;호제법의\;과정을\;나열하면\;아래와\;같다.$$

$$a\;+\;b(-q_{1})\;=\;r_{2}\;\Rightarrow\;ax_{2}\;+\;by_{2}\;=\;r_{2}\Rightarrow\;a(x_{0}\;-\;x_{1}q_{1})\;+\;b(y_{0}\;-\;y_{1}q_{1})\;=\;r_{2}$$

$$a(-q_{2})\;+\;b(1+q_{1}q_{2})\;=\;r_{3}\;\Rightarrow\;ax_{3}\;+\;by_{3}\;=\;r_{3}\Rightarrow\;a(x_{1}\;-\;x_{2}q_{2})\;+\;b(y_{1}\;-\;y_{2}q_{2})\;=\;r_{3}$$

$$...$$

$$ax_{n}\;+\;by_{n}\;=\;r_{n}\;\Rightarrow\;a(x_{n-2}\;-\;x_{n-1}q_{n-1})\;+\;b(y_{n-2}\;-\;y_{n-1}q_{n-1})\;=\;r_{n}$$

$$ax_{n+1}\;+\;by_{n+1}\;=\;r_{n+1}\;\Rightarrow\;a(x_{n-1}\;-\;x_{n}q_{n})\;+\;b(y_{n-1}\;-\;y_{n}q_{n})\;=\;r_{n+1}$$

$$ax_{n+2}\;+\;by_{n+2}\;=\;r_{n+2}\;\Rightarrow\;a(x_{n}\;-\;x_{n+1}q_{n+1})\;+\;b(y_{n}\;-\;y_{n+1}q_{n+1})\;=\;r_{n+2}$$

$$r_{n+2}\;가\;(a,b)\;가\;되는\;순간\;아래\;식의\;해가되는\;정수쌍을\;구하게\;된다.$$

$$ax_{n+2}\;+\;by_{n+2}\;=\;r_{n+2}\;=\;(a,b)$$

$$알고리즘의\;초기\;조건은\;아래와\;같다.$$

$$r_{0}\;=\;a,\;r_{1}\;=\;b\;로\;한다.$$

$$ax_{0}\;+\;by_{0}\;=\;r_{0}\;=\;a\;를\;성립하는\;해는\;x_{0}\;=1,\;y_{0}\;=\;0$$

$$ax_{1}\;+\;by_{1}\;=\;r_{1}\;=\;b\;를\;성립하는\;해는\;x_{1}\;=0,\;y_{1}\;=\;1$$

참고 - 유클리드 호제법 - 위키백과