유클리드 호제법 증명
유클리드 호제법 (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
증명 과정 그림 설명
** mod 와 뺄셈 과정 정리하기
나머지를 구한다는 건 더 이상 뺄 수 없을 때까지 뺀다는 것 (몫과 나머지를 구하는 과정 모두 내부는 뺄셈)
곱셈은 여러번 더하는 것
** 증명 외에 직관적으로 과정을 이해할 수 있도로 표현한 그림 더 찾기