[알고리즘] 유클리드 알고리즘(유클리드 호제법)

이산수학 보강 수업에서 유클리드 알고리즘에 대해 배웠다. 1학년 때부터 계속 배웠던건데 이번으로 3번째 정도 들으니까 좀 알겠더라..

---

유클리드 알고리즘(유클리드 호제법)이란 2개의 자연수의 최대공약수를 쉽게 알아낼 수 있는 알고리즘이다.
최대공약수란 두 정수를 나누어 떨어지게 하는 수 중 가장 큰 정수를 의미한다.

두 정수 A, B의 최대공약수 k를 구해보자 (A > B)
A = B * q + r 이라고 할 수 있다. (q는 몫, r은 나머지)
A와 B의 최대 공약수는 k이므로 A = k·A', B = k·B' 라고 하자. (A'과 B'은 서로소)
그러면 k·A' = ( k·B') * q + r 이다.
이때, r =  k·A' - ( k·B') * q 라고 쓸 수 있다.
r =  k(A' - B'·q)이므로 r 역시 k를 약수로 가진다.
r = k·r' = k(A' - B'·q)
r' = A' - B'·q
그렇다면 여기서 B'과 r'이 서로소임을 보이면
k는 A와 B의 최대공약수이면서 B와 r의 최대공약수이라는 것을 보일 수 있다.

B'과 r'이 서로소가 아니라 p라는 공약수를 가진다고 가정해보자
그러면 B' = p·B'', r' = p·r''이라고 할 수 있다.
 A = k·A' = ( k·B') * q + r 식에 대입하면
 A = ( k·p·B'') * q + k·p·r'' 이므로 A는 p·k를 약수로 가진다.
그러면 A와 B의 공약수가 k·p가 되는데, A와 B의 최대 공약수가 k라고 가정했으므로 여기서 모순이 발생한다.
따라서 B'과 r'은 서로소이므로
k는 A와 B의 최대공약수이면서 B와 r의 최대공약수라고 할 수 있다. 

이 증명을 바탕으로 하는 유클리드 알고리즘을 활용하면
A와 B의 최대공약수를 구하는 대신 수의 크기가 더 작은 B와 r의 최대공약수를 구하는 방식으로
더 빠르고 쉽게 A와 B의 최대공약수를 구할 수 있다.

---

예를 들어 1232와 374의 최대공약수를 유클리드 알고리즘을 이용해 구해보자

1232 = 374 * 3 + 110
따라서 1232와 374의 최대공약수는 374와 110의 최대공약수와 같다
gcd (1232, 374) = gcd(374, 110)

374 = 110 * 3 + 44
따라서 374와 44의 최대공약수는 110과 44의 최대공약수와 같다
gcd (374, 110) = gcd(110, 44)

110 = 44 * 2 + 22
따라서 110과 44의 최대공약수는 44와 22의 최대공약수와 같다
gcd(110, 44) = gcd (44, 22)

44 = 22 *2 + 0 
나머지가 0이므로 44와 22의 최대공약수는 22이다.
gcd (44, 22) = gcd(22, 0) = 22