최대공약수를 구하는 유클리드 호제법 증명하기.
유클리드 호제법으로 최대 공약수를 쉽게 구할 수 있다.
예를 들어, (16, 12) 란 값이 있을 때 이 두 수의 최대공약수를 구하려면
(A, B)
(B. (A%B))
..
..
..
(R, 0)
이 된다. 그러면 여기서의 R 이 최대공약수가 된다. 이해를 못 하시겠다구요? 그러면 숫자를 사용해봅시담
(16, 12)
(12, 4)
(4, 0)
즉 (16, 12) 의 최대공약수는 4가 됩니다. 정말 쉽죠?
그래서 직접 코드 유클리드 호제법을 사용하면 O(log N) 이 나올 것이다.
이제 유클리드 호제법을 한 번 증명해보자. 증명은 고등학교 이후로 처음하는 것 같다.
자연수 A, B 가 있다.
A % B = q
A / B = r
라고 하자.
G(A, B) 가 있을 때 G 함수는 최대 공약수를 구해주는 함수라고 할 때 G(A, B) = G(B, q) 이다.
위에 있는 식을 정리하면 (A = r x B + q) 일 것이다.
최대 공약수를 구하기 위해
A = mp
B = np
라고 해보자.
위의 (A = r x B + q) 에 대입을 해주면
(mp = r x np + q) 일 것이다.
!!! 여기서 m 과 n 은 서로소이다. p 를 공약수라고 생각하자 !!!
지금 G(A, B) = G(B, q) 를 증명하는 것이기 때문에, 다시 식을 q 를 기준으로 정리를 하면
q = (mp - r x np) 일 것이다.
p 로 묶어주면 다음과 같다.
q = (m - r x n)p
이제 해당 식을 보면 알 수 있 듯이
q 에는 b 와 r의 공약수이다. 그렇다면 이 q 가 최대 공약수임을 보일려면, n 과 (m- rn) 가 서로소여야 된다.
서로소임을 보이기 위해 귀류법을 사용하도록 하겠다.
만약 n 과 (m-rn) 이 서로소가 아닐 때! 이 둘은 서로 어떤 공약수를 가지고 있을 것이다.
즉,
n = vh,
(m-rn) = sh
라고 했을 때 (h는 1이 아님)
vh = sh - r x vh 이다.
m = sh + r x vh, 이고 묶으면 m = (s + rv)h 이다
그런데 위에서 (!!! 여기서 m 과 n 은 서로소이다 !!!) 라고 써놨다. 근데? m 이 h 를 가지고 있다. 그리고 n 도 h 를 가지고 있다.
이 2두가지 사실은 위에 서로소임을 말한 것에 반대된다.
즉, m 과 n-q 는 서로소이기 때문에 G(B, r) = G(A, B) 가 된다.
증명은 끝났다. 하지만 이걸 증명하기 위해 % 도 증명을 해야하고 정수론 이런 것도 나오는데 패스한다.
반응형