Euclid의 호제법

252로 105를 위한 Euclid의 호제법의 애니메이션.
크로스바는, 최대공약수(GCD)인 21의 배수를 나타낸다.
각각의 스텝에 대하고, 1개의 번호가 제로가 될 때까지, 보다 적은 수는 보다 큰 수로부터 끌린다.
나머지의 수는, GCD.

Euclid의 호제법(Euclid의 상조 편, 영: Euclidean Algorithm)은, 2개의 자연수의 최대공약수를 요구하는 방법의 하나이다.

2개의 자연수 a, b (a≥b)에 대해서, a의 b에 의한 잉여를 r로 하면, a와 b와의 최대공약수는 b와 r와의 최대공약수에 동일하다고 하는 성질이 성립된다.이 성질을 이용하고, b를 r로 나눈 잉여, 제수 r를 그 잉여로 나눈 잉여, 라고 잉여를 요구하는 계산을 순서대로 반복하면, 잉여가 0이 되었을 때의 제수가 a와 b와의 최대공약수가 된다.

명시적으로 기술된 최고의 알고리즘으로서도 알려져 기원 전 300년경에 기록된 Euclid의 「원론」 제7권, 명제 1에서 3이 그래서 있는[^{주석 1}].

목차

예

(문제) 1071으로 1029의 최대공약수를 요구한다.

• 1071을 1029로 나눈 나머지는 42
• 1029를 42로 나눈 나머지는 21
• 42를 21으로 나눈 나머지는 0

따라서, 최대공약수는 21이다.

증명

a, b는 자연수로 a≠0으로 한다. b를 a로 나눈 상을 q, 잉여를 r로 하면

b = qa + r

지금, d₀를 a와 r의 양쪽 모두를 결론 짓는 자연수로 한다.

이 때 d₀는 적qa를 결론 짓기 때문에, 화qa + r도 결론 짓지만, qa + r는 b에 동일하다.따라서, d₀는 a와 b를 결론 짓는다.즉 a와 r의 공약수는 모두 b와 a의 공약수이다.

반대로, d₁를 b와 a의 양쪽 모두를 결론 짓는 자연수로 한다.

d₁는 qa를 결론 짓기 때문에 차이 b - qa를 결론 짓지만, b - qa는 r에 동일하다.따라서, d₁는 a와 r를 결론 짓는다.바꾸어 말하면 b와 a의 공약수는 모두 a와 r의 공약수이다.

따라서, b와 a의 공약수 전체의 집합은 a와 r의 공약수 전체의 집합에 동일하고, 특히 b와 a의 최대공약수는 a와 r의 최대공약수가 아니면 안된다.

수속적 기술

 

Euclid의 호제법의 구조는, 이 그림과 같이 최대공약수를 요구하는 대상의 2개의 정수를 폭과 높이로 설정한 장방형내에서의 적색의 경사째의 직선의 묘화 과정에 의해도 표현할 수 있다. 적색의 경사째의 직선의 묘화는, 처음은 그 장방형내를 묘화 범위로 해, 그 모퉁이에서 내부로 향해서 한편, 그쯤 대해 45도의 차이를 갖게해 개시한다. 묘화 범위의 옆의 도중에 해당되면, 그 내부에 직각 반사하도록(듯이) 각도를 바꾼다. 적색의 경사째의 직선이 반사 후에 묘화 범위의 정면의 옆과 다른 옆의 도중에 해당되는 경우, 묘화 범위의 장변의 길이를 단변의 길이로 나누면 나머지가 생기는 상태가 되고 있어 직전의 반사 지점을 발판에 묘화 범위를 수직에 단락지어 그 범위를 좁힌다. (단락지어져 할 수 있던 작은 편의 범위를 이후의 묘화 범위로 한다) (제수 및 피제수의 변경에 상당) 적색의 경사째의 직선이 묘화 범위의 모퉁이에 도달했을 경우, 묘화 범위의 장변의 길이를 단변의 길이로 남아 없게 갈라지는 상태가 되고 있어 묘화의 종료가 되어, 마지막에 해 최소의 묘화 범위(복숭아색의 범위)의 단변의 길이가 최대공약수가 된다.

수속적으로 기술하면, 다음 같게 된다.

1. 입력을 m, n (m≥n)로 한다.
2. n = 0이라면, m를 출력해 알고리즘을 종료한다.
3. m를 n로 나눈 나머지를 새롭게 n로 해, 더욱 원래의 n를 새롭게 m로 해 2. 에 돌아온다.

상기의 순서는 「n, m에 대해서 잉여의 연산을 실시할 수 있다」라고 하는 가정인 만큼 의는 있으므로, 정수환 만이 아니게 임의의 Euclid정역에 대해도 똑같이 해 최대 공약 인자를 요구할 수 있다.

확장된 호제법

정수 m, n의 최대공약수(영: Greatest Common Divisor)를 gcd(m, n)와 나타낼 때, (확장된) Euclid의 호제법을 이용하고, mx + ny = gcd(m, n)의 해가 되는 정수 x, y의 조를 찾아낼 수 있다.위의 예의 경우, m = 1071, n = 1029 때,

1071 = 1×1029 + 42

1029 = 24×42 + 21

42 = 2×21

이기 때문에, gcd(1071, 1029) = 21이며,

21 = 1029－24×42 

= 1029－24×(1071－1×1029)

= －24×1071 + 25×1029

되므로, x =－24, y = 25이다.

특히, m, n가 서로 소(최대공약수가 1)인 경우, mx + ny = 1의 정수해를(x, y)로 하면, mx + ny = c는 임의의 정수 c에 대해서 정수해(cx, cy)를 가지는 것을 안다.

일반적으로,${\displaystyle m=r_{0},n=r_{1}}$  에 두고, Euclid의 호제법의 각 과정을 반복해

${\displaystyle r_{0}=k_{0}r_{1}+r_{2}\ \ (0<r_{2}<r_{1})}$ 

${\displaystyle r_{1}=k_{1}r_{2}+r_{3}\ \ (0<r_{3}<r_{2})}$ 

${\displaystyle r_{2}=k_{2}r_{3}+r_{4}\ \ (0<r_{4}<r_{3})}$ 

${\displaystyle ...}$ 

${\displaystyle r_{h-1}=k_{h-1}r_{h}+0}$ 

하지만 얻을 수 있을 때,

${\displaystyle {\begin{pmatrix}r_{0}\\r_{1}\\\end{pmatrix}}={\begin{pmatrix}k_{0}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{1}\\r_{2}\\\end{pmatrix}}}$ 

${\displaystyle {\begin{pmatrix}r_{1}\\r_{2}\\\end{pmatrix}}={\begin{pmatrix}k_{1}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{2}\\r_{3}\\\end{pmatrix}}}$ 

${\displaystyle {\begin{pmatrix}r_{2}\\r_{3}\\\end{pmatrix}}={\begin{pmatrix}k_{2}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{3}\\r_{4}\\\end{pmatrix}}}$ 

${\displaystyle ...}$ 

${\displaystyle {\begin{pmatrix}r_{h-1}\\r_{h}\\\end{pmatrix}}={\begin{pmatrix}k_{h-1}&1\\1&0\\\end{pmatrix}}{\begin{pmatrix}r_{h}\\0\\\end{pmatrix}}}$ 

즉

${\displaystyle {\begin{pmatrix}r_{0}Y\r_{1}Y\\end{pmatrix}}={\begin{pmatrix}k_{0}&1YY1&0Y\\end{pmatrix}}{\begin{pmatrix}k_{1}&1YY1&0Y\\end{pmatrix}}{\begin{pmatrix}k_{2}&1YY1&0Y\\end{pmatrix}}{\begin{pmatrix}k_{3}&1YY1&0Y\\end{pmatrix}}...{\begin{pmatrix}k_{h-1}&1YY1&0Y\\end{pmatrix}}{\begin{pmatrix}r_{h}\Y0Y\\end{pmatrix}}}$ 

여기서

${\displaystyle K_{i}={\begin{pmatrix}k_{i}&1\\1&0\\\end{pmatrix}}}$  멀고와${\displaystyle |K_{i}|=-1}$  이기 때문에${\displaystyle K_{i}^{-1}}$ (은)는 존재해

${\displaystyle {\begin{pmatrix}k_{h-1}&1YY1&0Y\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{h-2}&1YY1&0Y\\end{pmatrix}}^{-1}...{\begin{pmatrix}k_{2}&1YY1&0Y\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{1}&1YY1&0Y\\end{pmatrix}}^{-1}{\begin{pmatrix}k_{0}&1YY1&0Y\\end{pmatrix}}^{-1}{\begin{pmatrix}r_{0}Y\r_{1}Y\\end{pmatrix}}={\begin{pmatrix}r_{h}\Y0Y\\end{pmatrix}}}$ 

이러한 과정에 대하고,${\displaystyle m=r_{0},n=r_{1}}$ , Euclid의 호제법에 의해,${\displaystyle r_{h}=\gcd(m,n)}$ 이기 때문에,${\displaystyle K_{i}^{-1}={\begin{pmatrix}0&1\\1&-k_{i}\\\end{pmatrix}}}$ (을)를 고려하면,

${\displaystyle {\begin{pmatrix}0&1YY1&-k_{h-1}Y\\end{pmatrix}}{\begin{pmatrix}0&1YY1&-k_{h-2}Y\\end{pmatrix}}...{\begin{pmatrix}0&1YY1&-k_{2}Y\\end{pmatrix}}{\begin{pmatrix}0&1YY1&-k_{1}Y\\end{pmatrix}}{\begin{pmatrix}0&1YY1&-k_{0}Y\\end{pmatrix}}{\begin{pmatrix}m\\n\\\end{pmatrix}}={\begin{pmatrix}\gcd(m, n)\Y0Y\\end{pmatrix}}}$ 

된다.

${\displaystyle {\begin{pmatrix}x&y\\u&v\\\end{pmatrix}}={\begin{pmatrix}0&1YY1&-k_{h-1}Y\\end{pmatrix}}{\begin{pmatrix}0&1YY1&-k_{h-2}Y\\end{pmatrix}}...{\begin{pmatrix}0&1YY1&-k_{2}Y\\end{pmatrix}}{\begin{pmatrix}0&1YY1&-k_{1}Y\\end{pmatrix}}{\begin{pmatrix}0&1YY1&-k_{0}Y\\end{pmatrix}}}$ 

(와)과 일어나 Euclid의 호제법의 각 과정에서 얻을 수 있었다 ${\displaystyle k_{0}}$ , ${\displaystyle k_{1}}$ , ${\displaystyle k_{2}}$ 등을 이용하고, 우변을 계산하면, 좌변의${\displaystyle x}$ , ${\displaystyle y}$  하지만 구해져, 이것은 베즈의 등식

${\displaystyle mx+ny=\gcd(m,n)}$ 

(을)를 채우는[⁶].

계산량

나누고 나머지를 취한다고 하는 조작을, 최악에서도 작은 분의 십진법으로의 자리수의 약 5배 반복하면, 최대공약수에 이른다(라메의 정리).

최대공약수를 요구하는데, 소인수 분해 해 보면 좋다고 생각하는 사람이 있을지도 모르지만, 이 정리는 소인수 분해를 이용하는 것보다도 Euclid의 호제법에 따르는 것이 훨씬 빠르다고 하는 것을 말하고 있다.

실제, 계산 complex system 이론에 있고는 최대공약수를 요구하는 것은 「용이한 문제」로서 알려져 있어 소인수 분해는 「곤란한 문제」여도 생각되고 있다. 입력된 2개의 정수의 쳐 작은 편의 정수 n의 자리수를 d라고 하면, Euclid의 호제법으로는 O(d) 회의 제산으로 최대공약수가 요구된다.자리수 d는 O(log n)이므로, Euclid의 호제법으로는 O(log n) 회의 제산으로 최대공약수가 요구된다.

연분수

위의 예로 나온, 1071으로 1029의 최대공약수를 요구하는 과정은, 다음 같게 나타낼 수 있다.

${\displaystyle {\begin{aligned}1071&=1029\times 1+42,\\1029&=42\times 24+21,\\42&=21\times 2.\end{aligned}}}$ 

즉,

${\displaystyle {\begin{aligned}{\frac {1071}{1029}}&=1+{\frac {42}{1029}},\\{\frac {1029}{42}}&=24+{\frac {21}{42}},\\{\frac {42}{21}}&=2.\end{aligned}}}$ 

따라서,

${\displaystyle {\frac {1071}{1029}}=1+{\frac {1}{24+{\frac {1}{2}}}}}$ 

이와 같이, n와 m (n > m)의 최대공약수를 요구할 때의 Euclid의 호제법의 나눗셈의 상은, 유리수 n/m의 연분수 전개가 되어 있다.

각주

[헬프]

주석

1. ^「원론」 제7권에서는, 1을 단위로 정의해, 2이상의 자연수를 수로 정의하고 있는[¹].

   정의

   1. 단위와는 존재하지만 각각이 거기에 따르고 1으로 불리는 것이다.
   2. 수와는 단위로부터 완성되는 다이다.
   Euclid의 호제법은 이하의 명제 1에서 3에 대해서 기술되어 있다.

   명제

   1. 두 개의 부등인 수가 정해져 항상 큰 수로부터 작은 수가 빼질 때, 만약 단위가 남겨질 때까지, 남겨진 수가 자신의 앞의 수를 결론 짓지 않는다면, 최초의 2수는 서로 순수하겠지[²].
   2. 서로 순수하지 않은 2수가 주어졌을 때, 그러한 최대공약수를 찾아내는 것[³].
      1. 지금부터 다음 일이 분명하다.즉 만약 있는 수가 두 개의 수를 결론 짓는다면, 그러한 최대공약수도 결론 지을 것이다.이것이 증명 해야 할것인[⁴].
   3. 서로 순수하지 않은 세 개의 수가 주어졌을 때, 그러한 최대공약수를 찾아내는 것[⁵].

출전

1. ^ Euclid&나카무라 외 1996, p. 149.
2. ^ Euclid&나카무라 외 1996, pp. 150f.
3. ^ Euclid&나카무라 외 1996, p. 151.
4. ^ Euclid&나카무라 외 1996, p. 152.
5. ^ Euclid&나카무라 외 1996, pp. 152f.
6. ^암굴 1983.

참고 문헌

• 암굴장경 「2 다음 행열의 세계」이와나미 서점〈수학 입문 시리즈 4〉, 1983년 4월 22일.ISBN 4-00-007634-5。
• 「Euclid 원론」하이베아・멘게편, 나카무라행시로・테라사카영 타카시・이토 슌타로우・이케다 미에역・해설, 공동설립 출판. - 전13권의 최초의 국역.
  • (하드 커버) 1971년 7월.ISBN 4-320-01072-8
    • (발췌)「세계의 명저 9」이케다 미에역중앙공론사 1972년
  • (축쇄판)1996년 6월.ISBN 4-320-01513-4
  • （추가 보충판）2011년 5월.ISBN 978-4-320-01965-2
• 「에우크레이데스 전집」(전5권), 하이베아・멘게편, 도쿄대학 출판회. - 「에우크레이데스 전집」의 세계 최초의 근대어역.
  • 제2권원론 VII－X, 사이토헌역・해설, 2015년 8월.ISBN 978-4-13-065302-2

관련 항목

• 베즈의 등식
• Euclid환

외부 링크

• 일본대백과 사전(닙포니카) 「Euclid의 호제법」-코트반크
• Weisstein, Eric W. "Euclidean Algorithm". MathWorld(영어). 

• Hazewinkel, Michiel, ed. (2001), "Euclidean algorithm", Encyclopaedia of Mathematics, Springer, ISBN 978-1-55608-010-4  CS1 maint: Date and year (link)

「https://ja.wikipedia.org/w/index.php? title=Euclid의 호제법&oldid=62797528」으로부터 취득

This article is taken from the Japanese Wikipedia Euclid의 호제법

This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.

Wikipedia and Tranpedia does not guarantee the accuracy of this document. See our disclaimer for more information.

In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.