유클리드 호제법의 이론과 실장

본고는'유클리드 상호제거법'의 총결과 (Python 3.x계)의 실현 스크립트를 자신이 대수 간의 최대 공약수를 신속하게 계산할 수 있는 계산 방법으로 삼는다.
공부 중이라 기술 내용이 틀릴 수 있습니다.이런 상황에서 죄송합니다. 댓글에 지적해 주셨으면 좋겠습니다.
※ 링크 대상 Qita 기사 저자 본인 전재.

유클리드의 상호 제곱법은?

큰 숫자의 최대 공약수를 빠르게 계산하는 방법.유클리드의 상호제곱법에서'상호제곱법'은'제법이 끝나기 전에 상호제곱법'이라는 뜻이다.
(산출량이 왜 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)

상술한 것은 왜 성립되었습니까?
세 단계로 나눠서 생각해보면 알겠지.

割り算の等式：a ÷ b = q あまり rが成り立つ時
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(33552379)=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과 1299340000의 최대 공약수를 요구하면 시간이 걸려 귀찮아 보인다.

# 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의 생략↩︎