유클리드 알고리즘이라고도 하는 유클리드 호제법은 너무 큰 두 수의 최대 공약수를 구하기 위한 알고리즘입니다.
유클리드 호제법이 뭔지부터 알아보자면
두수 a,b가 있고 a% b 값을 r이라 할 때 gcd(a, b)는 gcd(b, r)과 같아서 점차 숫자의 크기를 줄여가며 최대공약수를 쉽게 구할 수 있게 해주는 방식입니다.
그럼 저희가 증명해야할 것이 바로 눈에 들어옵니다.
바로 gcd(a,b) = gcd(b, r)이라는 것이죠.
단계적으로 증명해 나가보죠.
먼저 a, b는 정수이고 a >= b라 가정합니다. gcd(a, b)나 gcd(b, a)나 같으므로 일반성에 영향을 끼치지 않는 조건이죠.
그러면 a = bq + r을 만족하는 유일한 정수 q, r이 존재합니다. 이때 0 <= r < b입니다.
gcd(a, b) = d a = dA, b = dB라고 합시다. 이때 A, B는 서로소입니다.
위키피디아에는 A, B가 그냥 서로소라고만 나와있어서 왜인지 궁금하신 분들이 저를 포함해 분명 계실텐데 만약 A,B가 서로소가 아니라 하면 gcd(A, B) = m이라고 가정해 봅시다. 그러면 A, B는 m이라는 약수를 가지고 있게 되고 위에 a = dA, b = dB에서 A와 B는 m으로 나눠지게 되게되므로 당연히 a와b도 m으로 나눠지고 a와b는 d의 배수이므로 당연히 d로도 나눠집니다. 그러면 a,b는 dm으로 나눠 진다는 뜻인데 이는 gcd(a,b)가 d라는 것과 모순됩니다. 따라서 A,B는 서로소 여야합니다.
반대로 a, b의 공약수 n이 최대공약수가 아니라면 gcd(A, B)는 1이 아니겠죠.
다시 유클리드 호제법으로 돌아와 a = dA, b = dB를 a = bq + r에 대입하면
dA = dBq + r 이 되고 dBq를 좌항으로 넘기면
dA - dBq = r
d(A-Bq) = r이 됩니다.
저희가 증명해야 할 것을 다시 상기해 보죠.
gcd(a, b) = gcd(b, r)이었죠.
gcd(a, b) = d이므로 b는 당연히 d라는 약수를 가지고 그럼 r이 d라는 약수를 가지는 것을 증명해야 합니다.
근데 위에서 r은 d(A-Bq)였죠. 네 r은 d의 배수입니다.
??? : 어라? 그럼 증명 끝인가요?
그럴 리가 없죠 저희는 d가 r과 b의 공약수란 것은 알아냈지만 최대 공약수인 것은 아직 증명하지 못했습니다.
그러면 어떻게 최대 공약수임을 증명할 수 있을까요
저희는 위에서 알아봤습니다. 두 수의 cd(공약수)가 gcd(최대공약수)이려면 두 수를 cd로 나눈 값이 서로소여야 하는 것이죠.
그러면 귀류법을 통해 gcd(b, r)이 d라는 것을 증명해 보겠습니다.
먼저 gcd(b, r) = d , b = dB , r = dR이라 합시다. 여기서 B와 R이 두수를 공약수로 나눈 값이죠.
그러면 귀류법이므로 만약 d가 최대공약수가 맞다면 1이여야할 gcd(B, R) 값은 1이 아닌 어떤 정수라고 가정해봅시다.
맨 처음에 말한 식 a = bq + r에서 위에서 말했던 것과 방금 말한 식을 대입하면
dA = dBq + dR 가 되죠.
그리고 gcd(B, R)은 1이 아닌 어떤 정수 g라고 해보죠.
그러면 B와 R은 어떤 두수 B'과 R'로부터
B = gB'
R = gR'
이 성립하겠죠.
그리고 이를 위 식에 대입하면
dA = dgB'q + dgR'
dA = dg(B'q+R')
A = g(B'q+R')이 되죠.
즉 g는 A의 약수가 되죠.
그런데 g는 B의 약수도 되죠 B = gB'이니깐요.
하지만 저희는 아까 위에서 B와 A는 서로소라고 했죠.
이는 gcd(B, R)의 g 1이 아닌 정수라는 가정으로부터 나타나는 모순이므로 gcd(B, R)은 1이 됩니다.
따라서 gcd(b, r) = d 임을 증명하게 되죠
'수학' 카테고리의 다른 글
| RSA deep dive (4) | 2023.03.05 |
|---|