[백준 알고리즘] Q1934 최소공배수

유클리드 호제법

1. 유클리드 호제법 정의

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.  [위키백과]

 예) GCD(30, 12) = GCD(30 % 12, 12) = GCD(6, 12) = 6

 예) GCD(72, 45) = GCD(72 % 45, 45) = GCD(27, 45) = GCD(45 % 27, 27) = GCD(18, 27) = GCD(27 % 18, 18) = GCD(9, 18) = 9

2. 유클리드 호제법 증명

 G(a, b) = k (k는 최대공약수, 0 < b < a)

 a = bq + r (r은 a % b 와 동일하기 때문에, a와b의 최대공약수와 r과 b의 최대공약수가 동일하다는 것을 증명하는 것이 핵심!)

 a = mk , b = nk (k는 최대공약수이기 때문에 m과 n은 공약수가 없는 서로소)

 위에 식에 대입을 하면, mk = nkq + r → r = k(m - nq)

 r은 k와 (m-nq)의 곱으로 이루어져있고, b는 n과 k의 곱으로 이루어져 있기 때문에 두 수는 k라는 공배수를 가지고 있다!

 여기서! n과 (m - nq)가 서로소 라면, k는 공배수가 아닌, 최대공약수이다!

 귀류법을 이용해서, n 과 (m - nq)가 서로소라고 가정을 하자!

 그렇다면, n =xG 이고 (m - nq) = yG 이다. n을 우측 식에 대입을 하면, m - xGq = yG → m = G(y + xq) 이다

 m은 G(y + xq) 이고, n은 xG이므로, 위에서 정의한 m과 n은 서로소라는 정의와 모순이 되기 때문에 n과 (m - nq)가 서로소라는 가정도 모순이 된다!

 따라서, n과 (m - nq)가 서로소이기 때문에, k는 b와 r의 최대공약수가 된다!

 G(a, b) = G(a % b, b) = k(최대공약수)

3. Java 구현