유클리드 호제법 | GCD, LCM

유클리드 호제법 정리

두 자연수의 최대공약수를 구하는 알고리즘입니다.

A ≥ B인 두 자연수 A, B에 대하여
A = qB + r를 만족하는 경우
G(A, B) = G(B, r)를 만족
G함수 : 입력(두 정수), 출력(두 정수의 최대 공약수)

GCD : Greatest Common Divisor, 최대 공약수

LCM : Least Common Multiple, 최소 공배수

---

유클리드 호제법 증명

증명할 것 : G(A, B) = G(B, r)

 

A ≥ B 인 두 정수 A, B에 대해서 최대공약수를 G로 했을 때 다음이 성립합니다.

1. A = Ga

2. B = Gb

 

결론 1 : a와 b는 서로소이다.

a와 b가 서로소가 아닌 경우(공약수로 k(k ≠ 1)를 가지는 경우) A와 B의 최대공약수 Gk가 되므로 모순 발생

 

A = pB + r 해당식을 정리하면 다음과 같습니다.

1. r = A - Bp

2. r = Ga - Gbp

3. r = G(a - bp) 

 

이를 통하여 r은 G의 배수임을 확인할 수 있습니다.

 

총정리해보면

1. A = Ga

2. B = Gb

3. r = G(a - bp)

 

여기서 목표인 G(A, B) = G(B, r) 임을 증명하기 위하여  a - bp와 b가 서로소임을 증명하면 됩니다.

 

가정 : a - bp와 b가 서로소가 아니라고 가정

두 수가 서로소가 아니므로 GCM인 c를 가지므로 다음과 같이 표현할 수 있습니다.

1. a - bp = c * n

2. b = c * m

(n과 m는 서로소)

 

2번 식을 1번 식에 대입하면 다음과 같습니다.

1. a - c * m * p = c * n

2. a = c * (mp + n)

 

a와 b를 최종적으로 정리하면 다음과 같습니다.

a = c * (mp + n)

b = c * m

 

1) c ≠ 1

결과 : a와 b는 1 외 공약수를 가지므로 a와 b는 서로소라는 결론 1에 모순 발생

 

2) c = 1

1. b = m

2. a - mp = n

3. a - bp = n

결과 : b = m이고 a - mp = n에서 m과 n이 서로소이므로 가정에서 모순 발생

 

결론 2 : 모든 경우에 대하여 모순이 발생하므로 b와 a - bp는 서로소가 되겠습니다.

 

최종 결론 : 결론 1과 결론 2에 따라서 G(A, B) = G(B, r)가 성립함을 증명할 수 있습니다.

---

유클리드 호제법 (GCD 구현)

1. 반복문을 통한 구현

def GCD(A, B):
    while B != 0:
        tmp = A % B
        A = B
        B = tmp
    return A

2. 재귀 함수를 통한 구현

def GCD(A, B):
    if B == 0:
        return A
    else:
        return GCD(B, A % B)

---

LCM 구현

def LCM(A, B):
	return A * B // GCD(A, B)