유클리드 호제법의 지굴과 구현

본고는 큰 수끼리의 최대 공약수를 재빠르게 구할 수 있는 계산 방법인 「유클리드의 호제법」에 대한 정리와 (Python3.x계에서) 실장 스크립트를 자신용으로 기사로 한 것입니다.

공부중이기 때문에 기술내용에 실수등 있을지도 모릅니다. 그 경우, 죄송합니다만 코멘트등으로 지적해 주시면 다행입니다.
※ 젠 에도 필자 본인이 전재 완료.

유클리드의 호제법이란?

유클리드의 「호제법」이란 「나누어질 때까지 너무 서로 나누어(제법) 계속한다」라고 하는 의미. 이것을 사용하여 큰 숫자들의 최대 공약수를 빠르게 계산하는 방법.
(계산량이 왜 O(log2N)가 되는지에 대해서는 후일 가필 예정.)

전제 1 최대 공약수란

둘 이상의 양의 정수의 공통 약수 중 가장 큰 숫자.

예를 들어 12와 18의 최대 공약수는 6.9와 120의 최대 공약수는 3. 1

전제 2 유클리드의 호제법은 왜 성립되는가

a와 b의 최대 공약수를 gcd(a, b)로 한다. 2

예를 들어 gcd(12, 18) = 6

割り算の等式：a = b * q + r
上記が成り立つ時
gcd(a, b) = gcd(b, r)

위가 왜 성립되는가?

3단계에 걸쳐 생각하면 알 수 있습니다.

割り算の等式：a = b * q + r
があるとき、gcd(a, b) = G1, gcd(b, r) = G2とします。

(1)
r = a - b * q = G1(a' - b' * q')と変形できます。
つまりrの約数にはG1があるわけです。gcd(b, r)はbとrの最大公約数なので下記が言えます。
gcd(r, b) >= gcd(a, b)
つまり、G2 >= G1

(2)
a = G2(b'' * q''　+ r'')と変形できます。
つまりaの約数にはG2があるわけです。gcd(a, b)はaとbの最大公約数なので下記が言えます。
gcd(a, b) >= gcd(r, b)
つまり、G1 >= G2

(3)
上記ふたつより、G1 = G2が言えます。

사용법

실제로 3355와 2379의 최대 공약수를 찾아 보는 것을

종이에 써 봅시다. (아래는 스터디 사프리 씨의 해설 사이트 에서 인용.)



곧 모르는 분은 상기와 전제로 말한 조건을 함께 생각해 봅시다.

a ÷ b = q あまり r ⇒ gcd(a, b) == gcd(b, r)

b ÷ r = q'あまりr' ⇒ gcd(b, r) == gcd(q', r')

이것을 상기의 화상과 동일한 구체예에 적용하면,

3355 ÷ 2379 = 1 あまり 976 ⇒ gcd(3355, 2379) == gcd(2379, 976)

2379 ÷ 976 = 2 あまり 427 ⇒ gcd(2379, 976) == gcd(976, 427)

...省略

122 ÷ 61 = 2あまり0 ⇒ gcd(122, 61) == gcd(61, 0) == 61

거슬러 올라가면 gcd(3355, 2379) == 61. 즉 gcd(a, b)는 끝까지 나누었을 때의 나누는 수와 동일한 것을 알 수 있습니다.

우선은 최대 공약수를 보통으로 낸다

평소에 나가 보자. 이것도 작은 수라면 시간이 걸리지 않고 풀 수 있습니다.

# first, secondのうち小さい方を最大値としてそこから-1ずつして両方を割り切れるものを探す
def boring_gcd_method(first, second):
    limit = min(first, second)
    # print("limit", limit)  # debug
    for i in range(limit, 0, -1):
        # print("i", i)  # debug
        if first % i == 0 and second % i == 0:
            return i  # int

유클리드의 호제법으로 발행

위의 방법으로도 좋습니다만, 예를 들면 239520000과 1293400200의 최대 공약수를 요구하는 것이라면 시간이 걸려 귀찮을 것 같습니다.

# a = b * q + r, gcd(a, b) == gcd(b, r)
def euclidean_algo(first, second): # good
    while second:
        first, second = second, first % second
        # print("first, second", first, second)  # debug
    return first  # int

참고 사이트

Studyplus 유클리드 호제법

고등학교 수학의 아름다운 이야기 유클리드 호제법 증명과 부정 방정식



덧붙여서 (이번은 관계 없지만) 「서로 소」란 최대 공약수가 1인 숫자끼리라는 것. 예를 들어 3과 10은 최대 공약수가 1이므로 서로 소소하다고 할 수 있다. ↩

Greatest common divisor의 약어 ↩