유클리드 호제법

$$유클리드\;호제법$$

$$유클리드\;호제법은\;영어로\;표기하면\;그냥\;Euclidean\;algorithm\;이다.$$

$$두\;수를\;서로\;나누어\;최대공약수를\;구하는\;방법\;이다.$$

$$정리$$

$$a, b\;가\;정수일\;때\;a를\;b로\;나눈\;나머지를\;r이라고\;하자\;( a \le b,\;0 \le r \le b)$$

$$a와\;b의\;최대공약수를\;(a,b)라고\;하면,\;다음이\;성립한다.$$

$$(a,b)\;=\;(b,r)$$

 

$$예시$$

$$(1071,1029)\;=\;(1029,42)\;=\;(42,21)\;=\;(21,0)\;=\;21$$

$$b,r이\;새로운\;a,b가\;되어\;(a,b)=(b,r)\;을\;반복한다$$

$$증명$$

$$a,b\;가\;정수이고,\;a \ge b\;라고 하자.$$

$$그러면,\;a\;=\;bq\;+\;r\;을\;만족하는\;유일한\;정수\;q,r이\;존재한다.\;이때\;0 \le r < b\;이다.$$

$$a,b\;의\;최대공약수를\;d\;라고\;하자.\;즉,\;(a,b)\;=\;d\;이다.$$

$$그러면,\;a\;=\;d\alpha\;,\;b\;=\;d\beta\;로\;표현\;할\;수\;있다.\;이\;때\;\alpha\;와\;\beta\;는\;서로소다.$$

$$a\;=\;bq\;+\;r\;에\;위\;식을\;대입하면,\;r\;이\;d\;의\;배수임을\;알\;수\;있다$$

$$\begin{align} d\alpha\;&=\;d\beta q\;+\;r\\ \alpha\;-\;d\beta q\;&=\;r\\d(\alpha\;-\;\beta q)\;&=\;r\end{align}$$

$$(\alpha\;-\;\beta q)\;=\;\gamma\;라고\;하면,\;r\;=\;d\gamma\;라고\;할\;수\;있다.$$

$$(a,b)\;=\;(b,r)\;즉,\;(d\alpha,\;d\beta)\;=\;(d\beta,\;d\gamma)\;이\;성립하려면,\;\beta\;와\;\gamma\;는\;서로소여야\;한다.$$

$$만약,\;\beta\;와\;\gamma\;가\;서로소가\;아니라면,\;1\;보다\;큰\;공약수\;d^{\prime}\;이\;존재하게\;된다.$$

$$d^{\prime}\;이\;1\;보다\;크므로\;dd^{\prime}\;>\;d\;이\;성립한다.$$

$$즉,\;b\;와\;r\;의\;최대공약수는\;d\;가\;아니라\;dd^{\prime}\;이\;된다.$$

$$\;(d\beta,\;d\gamma)\;=\;(dd^{\prime}\beta,\;dd^{\prime}\gamma)\;=dd^{\prime}\;\neq\;d\;=\;(d\alpha,\;d\beta)\;=(a,b)$$

$$즉,\;(a,b)\;=\;(b,r)\;이\;성립하지\;않게된다.$$

$$\beta\;와\;\gamma\;가\;서로소임을\;증명하면\;위\;정리는\;성립한다.$$

$$\beta\;와\;\gamma\;가\;서로소가\;아니면,\;모순이\;발생하는지\;귀류법을\;통해\;증명해보자.$$

$$만약,\beta\;와\;\gamma\;가\;서로소가\;아니면\;즉, \;(\beta,\;\gamma)\;>\;1\;이면$$

$$\beta\;=\;d^{\prime}\beta^{\prime},\;\gamma\;=\;d^{\prime}\gamma^{\prime}\;로\;둘\;수\;있다.$$

$$a\;=\;bq\;+\;r\;에\;위\;식들을\;대입해보면,\;모순이\;발생하는\;것을\;볼\;수\;있다.$$

$$d\alpha\;=\;d\beta q\;+\;d\gamma\;=\;dd^{\prime}\beta^{\prime}q\;+\;dd^{\prime}\gamma^{\prime}\;=\;dd^{\prime}\;(\beta^{\prime}q\;+\;\gamma^{\prime})$$

$$\alpha\;=\;d^{\prime}\;(\beta^{\prime}q\;+\;\gamma^{\prime})\;로\;\alpha\;는\;d^{\prime}\;의\;배수가\;된다.$$

$$\alpha\;와\;\beta\;는\;서로소이어야\;하는데,\;1\;보다\;큰\;공약수가\;d^{\prime}\;이\;존재하므로,\;모순이\;발생한다.$$

$$(\beta,\;\gamma)\;=\;d^{\prime}\;>\;1\;라는\;가정에서\;나타나는\;모순이므로\;(\beta,\;\gamma)\;=\;1\;이다.$$

$$따라서,\;(b,r)\;=\;d\;=(a,b)\;로\;(a,b)\;=\;(b,r)\;이\;성립한다.$$

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