제비의 리(除比의 理)의 활용 ④ : 인류 역사상 가장 오래된 알고리즘 (유클리드 호제법)

[재후]

[제비의 리(除比의 理)]의 활용 ④ 

- 인류 역사상 가장 오래된 알고리즘

[제비의 리(除比의 理)]는

매우 강력한 공식입니다.

여기에서는

[제비의 리(除比의 理)]를 활용하여,

인류 역사 상

가장 오래된 알고리즘으로 알려진

'유클리드 호제법(Euclidean-algorithm)'을

증명해보겠습니다.

---

유클리드 호제법

(Euclidean-algorithm)

2개의 자연수(또는 정식) b, a에 대해서(단, b>a) 

b를 a로 나눈 나머지를 r이라 하면, 

b와 a의 최대공약수는 a와 r의 최대공약수와 같다. 

유클리드 호제법(互除法, Euclidean algorithm)

또는

유클리드 알고리즘은 

2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 

알고리즘의 하나입니다.

예를들어

78696과 19332의

약수에 대해 생각해보겠습니다.

편의 상...

양의 약수만 생각해보겠습니다.

필요한 데이터를 알아내기 위해

다음과 같이

두 수의 약수와 공약수를 구하는

Python 코드를 작성하였습니다.

import math

"""b를 a로 나눈 몫을 리턴함"""

def q(b, a):

    if a == 0:

        return None #raise   Exception("0으로 나눌수 없습니다.")

    if a>0:

        return math.floor(b/a)

    if a<0:

        return math.ceil(b/a) # 혹은 -math.floor(-b/a)

"""b를 a로 나눈 나머지를 리턴함"""

def r(b, a):

    if a==0:

        return None

    return b - a * q(b,a)

"""b를 a로 나눈 몫과 나머지를 리턴함"""

def qr(b, a):

    if a==0:

        return None, None

    return q(b, a), r(b, a)

"""b의 약수를 리턴함"""

def divisor_list(b):

    my_divisor_list = []

    for i in range(1, b+1):

        if r(b, i)==0:

            my_divisor_list.append(i)

    return my_divisor_list

"""b, a의 공약수를 리턴함 (b>a)"""

def common_divisor_list(b, a):

    if a>b:

        b, a = a, b

    my_common_divisor_list = []

    for i in range(1, a+1):

        if r(a, i)==0 and r(b, i)==0:

            my_common_divisor_list.append(i)

    return my_common_divisor_list

if __name__ == "__main__":

    b = 78696

    a = 19332

    print("\n\n", "%d's divisor_list: "%(b), "\n", divisor_list(b))

    print("\n\n", "%d's divisor_list: "%(a), "\n", divisor_list(a))

    print("\n\n", "(%d, %d)'s common_divisor_list: "%(b, a), "\n", common_divisor_list(b, a))

=======================

출력값:

78696's divisor_list: [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72, 1093, 2186, 3279,

4372, 6558, 8744, 9837, 13116, 19674, 26232, 39348, 78696] 19332's divisor_list: [1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108, 179, 358, 537,

716, 1074, 1611, 2148, 3222, 4833, 6444, 9666, 19332] (78696, 19332)'s common_divisor_list: [1, 2, 3, 4, 6, 9, 12, 18, 36]

즉

실행 결과는 다음과 같습니다.

78696의 약수: 

1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72, 1093, 2186, 3279, 

4372, 6558, 8744, 9837, 13116, 19674, 26232, 39348, 78696

19332의 약수: 

1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108, 179, 358, 537, 

716, 1074, 1611, 2148, 3222, 4833, 6444, 9666, 19332

78696, 19332의 공약수:

1, 2, 3, 4, 6, 9, 12, 18, 36

이상을 종합하면

다음 사실을 알 수 있습니다.

78696, 19332의 최대공약수:

36

이것을

다음과 같이 나타냅니다.

gcd(78696, 19332) = 36

이제

유클리드 호제법을 이용하여

같은 결과를 얻어낼 수 있습니다.

---

증명에 들어가기 전에...

몇 가지 알아야 할 간단한 사실이 있습니다.

만약 d가 

b, a의 공약수라면

다음과 같은 꼴로 쓸 수 있습니다.

b = d × m

a = d × n 

예를 들면

12는 

78696, 19332의 공약수이므로

78696 = 12 × 6558

19332 = 12 × 1611

또한...

다음 두 개의 식을 살펴보겠습니다.

자연수 범위에 한정해서 s, t, u, v를 생각하겠습니다.

자연수 t의 값에 따라 

자연수 s는 다양한 값을 가지게 됩니다.

그 중 t = 3일 때, 

s는 최소의 자연수 값 4를 가지게 됩니다.

또한

자연수 v의 값에 따라 

자연수 u는 다양한 값을 가지게 됩니다.

그 중 v = 3일 때, 

u는 최소의 자연수 값 4를 가지게 됩니다.

즉

s의 최소값과 u의 최소값은 

같습니다.

min(s) = min(u) = 4

왜 같은 것일까요?

다음과 같은 이유 때문입니다.

12/9 = 8/6 = 4/3

또한

s가 최소값을 가지도록 하는( min(s) = 4 ) t의 최소값과

u가 최소값을 가지도록 하는( min(u) = 4 ) v의 최소값은

일치합니다.

min(t) = min(v) = 3

이유는 마찬가지입니다.

다음과 같은 이유 때문입니다.

12/9 = 8/6 = 4/3

다른 식인 것처럼 보이지만

기약분수로 고쳐서 나타내보면

사실은 같은 식이었던 것입니다.

---

유클리드 호제법

독자적인 증명법

유클리드 호제법(Euclidean algorithm)은

인류 역사 상

명시적으로 기술된

가장 오래된 알고리즘으로 알려져 있으며,

기원전 300년경에 쓰인

유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.

(증명)

유클리드 호제법을 증명하는 방법은 다양하겠지만

여기에서는

'공약수 중 최대값이 최대공약수'라는 사실과

[제비의 리(除比의 理)]를 활용하여

독자적인 증명법을 보이겠습니다.

b를 a로 나눈 몫을 Q, 나머지를 R이라 합시다.

유클리드 호제법은 다음과 같습니다.

gcd(b, a) = gcd(a, R)

이것을 증명하고자 합니다.

이제

b, a의 공약수를 u,

a, R의 공약수를 v라 합니다.

공약수 중 최대값이 최대공약수이므로

u의 최대값 max(u)와 

v의 최대값 max(v)가 

같음을 보이면 됩니다.

u는 b, a의 공약수이므로

b = u×s, a = u×t

v는 a, R의 공약수이므로

a = v×y, R = v×z

따라서

u = b/s = a/t … ①

v = a/y = R/z … ②

①에서

b/a = s/t

여기에 [제비의 리(除比의 理)]를 적용하면

R/a = s'/t … ③

(단, R은 b를 a로 나눈 나머지, s'는 s를 t로 나눈 나머지)

또한 ②에서

R/a = z/y … ④

③, ④에서

R/a = s'/t = z/y … ⑤

위와 같이

R/a는 분수입니다.

분수는 (s', t) 혹은 (z, y)를 변화시켜

많은 방법으로 나타낼 수 있습니다.

이를테면 12/9 = 8/6 = … 처럼...

하지만 그러한 분수들을 

기약분수로 통일하여 같게 나타낼 수도 있습니다.

이를테면 12/9 = 8/6 = 4/3 = … 처럼...

기약분수로 나타냈을 때 

그 분수의 분모, 분자는 최소가 됩니다.

12/9 = 8/6 = 4/3 = … 처럼...

즉

⑤에서

분수 R/a에 대한 또 다른 분수 표현식인

s'/t 및 z/y 각각의 경우

(s', t) 혹은 (z, y)를 변화시켜 다양한 표현을 얻을 수 있지만

기약분수로 나타내면 그 표현이 같아지고

바로 그때

각각의 분모는 최소값이 되고 같을 수 밖에 없는 것입니다.

즉

min(t) = min(y) … ⑥

이를테면

A/B의 값은 분모 B의 값이 작을수록 커집니다.

그리고 B의 값이 최소가 될 때 A/B의 값은 최대가 될 것입니다.

min(t)를 ①에 적용하면

max(u) = a / min(t) … ⑦

min(y)를 ②에 적용하면

max(v) = a / min(y) … ⑧

⑥이 성립하므로

결국 ⑦, ⑧에서 다음을 얻게 됩니다.

max(u) = max(v)

max(u)는 b, a의 공약수 u 중에서 최대값이므로 gcd(b, a) 입니다.

즉, max(u) = gcd(b, a)

max(v)는 a, R의 공약수 v 중에서 최대값이므로 gcd(a, R) 입니다.

즉, max(v) = gcd(a, R)

따라서

max(u) = max(v) 이므로

gcd(b,a) = gcd(a, R) … ⑨

R은 b를 a로 나눈 나머지이므로

R = [b]_a

따라서

⑨는 다음과 같습니다.

gcd(b, a) = gcd(a, [b]_a)

¶ 증명 끝

---

계산 사례

78696과 19332의

최대공약수를 구하면,

    78696 ＝ 19332×4 ＋ 1368

    19332 ＝ 1368×14 ＋ 180

     1368 ＝ 180×7 ＋ 108

      180 ＝ 108×1 ＋ 72

      108 ＝ 72×1 ＋ 36

       72 ＝ 36×2 ＋ 0

나머지가 0이 되기 전

마지막 나머지인 36이

바로 78696과 19332의 최대공약수가 되는 것입니다.

즉

gcd(78696, 19332)

=

gcd(19332, 1368)

=

gcd(1368, 180)

=

gcd(180, 108)

=

gcd(108, 72)

=

gcd(72, 36)

=

gcd(36, 0)

=

36

혹은

gcd 라는 함수명을 제외하고 

다음과 같이 간략하게 표기하는 경우도 많습니다.

(78696, 19332)

=

(19332, 1368)

=

(1368, 180)

=

(180, 108)

=

(108, 72)

=

(72, 36)

=

(36, 0)

=

36

나머지 기호를 써서

중간 과정을 명시적으로 나타낸다면...

(b, a) = (a, [b]_a)

(78696, 19332) = (78696, [78696]₁₉₃₃₂)

=

(19332, 1368) = (19332, [19332]₁₃₆₈)

=

(1368, 180) = (1368, [1368]₁₈₀)

=

(180, 108) = (180, [180]₁₀₈)

=

(108, 72) = (108, [108]₇₂)

=

(72, 36) = (72, [72]₃₆)

=

(36, 0) = 36

[어은]

추천 드립니다.^^