최대 공약수 (With. 유클리드 호제법)

유클리드 호제법

호제법(互除法)이라는 말은 서로(互) 나누기(除)라는 뜻으로 그리스의 수학자 유클리드의 저서 원론에 적혀있는 최초의 알고리즘으로서  최대공약수를 구하는 방법이다.

 

명제 및 알고리즘

두 양의 정수 a, b(a > b)에 대하여 gcd(a, b) = gcd(a, (b mod b))이다

gcd(a, b)는 a, b의 최대공약수를 뜻하며 a mod b는 a를 b로 나눈 나머지이다.

 

파이썬 알고리즘은 다음과 같다

def E(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

---

증명

gcd(a, b) = G 라하면 적당한 서로수인 정수 A, B에 대해 a = GA, b = GB가 성립한다.

이를 a = bq + r에 대입하면

GA = GBq + r이고

r = G(A - Bq)이다.

 

한편, A - Bq와 B의 관계가 gcd(B, A - Bq) = m (m ≠ 1) 즉, A - Bq와 B가 서로소가 아니라고 한다면

B = mk, A - Bq = ml이 성립한다.

A = ml + Bq = ml +mkq = m(l + kq)이므로

m은 A와 B의 공약수임을 알수 있다.

그런데 A, B는 서로수 이므로 m = 1이 된다.

처음 가정했던 m ≠ 1과 모순이므로 m≠ 1이 틀렸고

즉, A - Bq와 B는 서로수 이고

"두 양의 정수 a, b(a < b)에 대하여 gcd(a, b) = gcd(b, (a mod b))이다"는 참인 명제가 된다.

---

활용

1298, 34782의 최대공약수

gcd(34782, 1298) = gcd(1298, 1034), 1298 mod 1034 = 1034

gcd(1298, 1034) = gcd(1034, 264), 1034 mod 264 = 242

gcd(1034, 264) = gcd(264, 242), 364 mod 242 = 22

gcd(264, 242) = gcd(242, 22), 242 mod 22 = 0

따라서 1298, 34782의 최대공약수는 22

---

참고문헌

Library of Koreandria 블로그 인류 최초의 알고리즘 - 유클리드 호제법

2021월 10월 29일 - 명제 및 알고리즘에서 a, b(a < b)를 a, b(a > b)로 수정

                          명제 및 알고리즘, 증명에서 gcd(a, (a mod b))를 gcd(b, (a mod b))로 수정

2021월 11월 18일 활용 부분에서 최소공배수 ->최대공약수로 변경 항상 헷갈림...