유클리드 호제법 증명

유클리드 호제법 (Euclidean algorithm) 증명 과정

 

(0) 유클리드 호제법이란

 

두 양의 정수 A와 B의 최대 공약수 (GCD; Greatest Common Divisor) 를 구한다.

A가 B 보다 더 크다면 (A > B), A 를 B로 나눈 나머지를 r 이라 할 때,

A와 B의 최대 공약수는 B와 r 사이의 최대 공약수와 똑같다.

 

 

예시

[출처 아는 형님]

 

어느 가게에서 개업 기념으로 풍선 245개와 행운권 210장을 준비하여 최대한 많은 손님들에게 남김없이 똑같이 나누어 주려고 합니다. 풍선과 행운권을 받을 수 있는 손님은 몇 명인가요? 

=> 245와 210 의 최대공약수는 210과 35의 최대공약수와 같다.

 

 

** 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. [출처]

---

증명 과정

[출처]

 

 

(1) A와 B의 관계를 최대공약수를 이용하여 표현

 

최대공약수를 G라고 하면, A = aG, B = bG 라고 표현할 수 있다.

 

최대 공약수라는 이름을 유지하기 위해서는 더 이상의 공약수가 없어야하므로 a와 b는 서로소라고 정의할 수 있다.

 

 

 

 

(2) A와 B의 관계를 몫과 나머지 관계로 표현

 

A를 B로 나눈 나머지가 r 이었을 때 (위의 유클리드 호제법 설명 (0) 참조),

B와 r 과의 최대 공약수도 G인지만 확인하면 된다.

 

A를 B로 나눈 몫을 q 라고 하면, A = qB + r 이 된다.

 

(1) 에서 A = aG, B = bG  라고 했으므로 이를 이용하면, A = qB + r은

 

aG = qbG + r 이 된다.

결과적으로 ∴ r = ( a - qb )G 가 된다.

 

 

 

(3) B와 나머지의 최대공약수가 G인지 확인

 

r = (a-qb)G가 되고 B = bG 니까, r과 B 사이 최대 공약수가 G 인지만 확인하면 된다.

 

a-qb 와 b 사이에 공통되는 약수가 없으면 (=서로소), r과 B의 최대 공약수도 G 가 된다.

 

이를 결과를 부정하는 귀류법으로 증명한다.

만약, 서로소가 아니라면 a-qb = mP, b = nP 이렇게 표현할 수 있다.

서로소가 아니라고 부정을 했기 때문에 공통인 약수 P 라는 놈을 서로 갖고 있을 것이다.

 

그러면 b = nP 로 바꿔주면,

a-qb = mP 는 a-qnP = mP 가 된다.

P로 묶어주면 a = (nq + m)P 가 된다.

 

 a = (nq + m)P

b = nP

 

그런데, 우리가 a 와 b 가 서로소라는 걸 알고 있다. ((1) 번 참고)

이렇게 표현하면 a와 b는 P라는 공약수가 있게 되는 것이다. 

a = (nq + m)P, b = nP

이렇게 되면 a와 b는 서로소가 아니다라는게 된다. 

a와 b 가 서로소라는 사실에 위배되는 것이기 때문에 

결과를 부정 (a-qb와 b 는 서로소가 아니다) 한 게 모순이 발생했으므로 

a-qb 와 b 는 서로소구나를 알 수 있게 된다.

 

이렇게 r=(a-qb)G와 B = bG 에서 a-qb 와 b는 서로소라는 것을 증명한 것이고,

결과적으로 r와 B의 최대 공약수도 G가 된다는 게 증명이 되는 것이다.

 

 

---

도형으로 표현한 유클리드 호제법

[출처]

198 x 120 인 직사각형의 바닥을 정사각형의 타일로 채우려고 할 때, 최소의 타일을 사용하려면 정사각형 타일 한 변의 길이를 얼마로 해야하는가?

 

198 x 120 의 바닥 크기이므로 첫번째 빨간색 정사각형의 한 변의 길이는 120 이다.

120 의 남는 변을 남는 길이인 78의 파란색 정사각형으로 채운다.

다음은 남는 세로 길이인 42의 초록색 정사각형으로 채운다.

이 과정을 계속해 나가면, 마지막으로 주황색의 가장 작은 6개의 정사각형으로 채워지게 된다.

이 때의 마지막 정사각형 한 변이 길이인 6이 최대 공약수이다.

 

---

소스코드 (Python)

def GCD(a,b):
	return f(b,a%b) if b else a

 

소스코드 (C)

int GCD(int a, int b){return b?f(b,a%b):a;}

---

참고 자료

 

유클리드 호제법 (수악중독)

https://www.youtube.com/watch?v=J5Yl2kHPAY4

 

유클리드 호제법 그림 설명

https://mathbees2.blogspot.com/2014/09/4_24.html 

 

증명 과정 그림 설명

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm 

 

 

** mod 와 뺄셈 과정 정리하기

나머지를 구한다는 건 더 이상 뺄 수 없을 때까지 뺀다는 것 (몫과 나머지를 구하는 과정 모두 내부는 뺄셈)

곱셈은 여러번 더하는 것

 

** 증명 외에 직관적으로 과정을 이해할 수 있도로 표현한 그림 더 찾기