최대공약수 구하기(알고리즘)

글을 시작하기 전에

예전부터 알고리즘을 풀어오며 소수나 최대공약수를 구하는 기법을 익히고 사용해왔다.
하지만 단순히 수식의 형태만 암기하여 활용 했을뿐 어떤 원리로 결과가 도출되는지
제대로 이해하지 않았었고 이번에 정리하며 글을 작성한다.

최대공약수 구하기 (추억 버전)

어릴적 학교에서 대부분 소수를 구하는 방법에 대해 공부했던 적이 있을것이다.

아마 위와 같은 방식으로 계산하는 방법을 배웠을 텐데 썩 괜찮아 보이는 방식이지만
계산할 숫자가 굉장히 커진다면 손으로 계산하는것이 불가능한 것은 물론이고 만약 저
방식으로 구현하여 알고리즘 문제를 해결하면 수행 시간의 벽에 부딪힐 것이다.

따라서 빠르게 최대공약수를 구하기 위해서는 새로운 기법이 필요하다.

유클리드 호제법

개념

호제법이란 두 수가 서로를 나누에서 원하는 값을 도출해 내는 알고리즘을 말하며
유클리드 호제법은 두 수가 서로를 나누에 가며 최대공약수에 도달하는 결과를
도출하는 알고리즘이다.

수행 예시

유클리드 호제법으로 14030와 13030의 최대 공약수를 구하는 예시이다.
14030 => A, 13030 => B 라고 가정했을때 A > B인 상태에서 계산을 시작해야 한다.

14030 % 13030 = 1000
13030 % 1000 = 30
1000 % 30 = 10
30 % 10 = 0
10

위와같이 A 와 B의 모듈러 연산을 수행한다.
그리고 결과값을 C 라고 가정하면 다시
B 와 C의 모듈러 연산을 수행한다.
위와 같은 패턴으로 반복하다 결과가 0이되면
B자리의 값이 바로 두 수의 최대공약수가 된다.

구현

n1, n2 = map(int, input().split())


def euclid(a, b):
    print(f'{a} % {b} = {a % b}')
    if a % b == 0:
        return b
    return euclid(b, a % b)


print(n1, n2)
print(euclid(n1, n2))

위와같이 재귀호출을 이용해서 매우 간단하게 최대공약수 도출 함수를 구현할 수 있다.

증명

다음으로 위의 계산식이 어떻게 성립하게 되는지에 대한 증명이다.

가장 먼저 G를 최대공약수라고 가정해보자
그리고 A = aG, B = bG 로 가정했을 때 G는 최대공약수 이므로
a와 b는 반드시 서로소 여야 한다.
다음으로 A는 B보다 큰 수 이므로 A = Bq + R 다음과 같은 수식을 세울 수 있다. (A % B = R)

위의 수식에 B = bG를 대입하면 A = bqG + R 이라는 수식정리할 수 있다.
R을 왼쪽에 남기고 나머지를 다 오른쪽으로 넘기면 R = A - bqG 로 정리가 되고
여기에 A = aG를 대입하면 R = aG - bGq = (a-bq)G 로 묶을 수 있다.
즉 R = (a-bq)G, B = bG 이므로 A % B 계산의 결과값인 R 또한 최대공약수 G를
가지고 있음을 알 수 있다.

다음으로 귀납적 추론을 통해 (a-bq)와 b가 과연 서로소가 맞는지에 대해 증명해 보겠다.

a-bq와 b가 서로소가 아니라고 전제한다면 각각 m이라는 최대공약수가 존재할 수 있다.
a-bq = mk, b = mk'라고 가정해보자 (이때 k와 k'는 서로소이다.)
a-bq = mk에 b = mk'를 대입하면 a-mk'q = mk 즉 a = m(k'q+k) 정리된다.

a = m(k'q+k), b = mk' 일때 맨 위의 가정에서 a와 b는 서로소라 전제 했으므로
m이 1이 아니라면 위의 전제조건 모순되게 되어 m은 1이 되어야 하고
a = k'q+k, b = k'가 되므로 a = bq+k, b = k' ===>>> k = a-bq, k' = b로
a-bq 와 b가 서로소가 되고 이는 위의 전제에 모순된다.
따라서 a-bq와 b가 서로소임이 증명된다.