유클리드 호제법

유클리드 호제법이란?

유클리드 호제법은 두수의 최대공약수를 구하기 위한 수학적 풀이입니다.

이방법은 매우 간단하면서도 효율적이며, 수학적으로도 정확합니다. 유클리드 호제법의 기본 아이디어는 두 수 a와 b의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수가 같다는 것입니다.

 

두수의 최대공약수를 유클리드 호제법을 사용해 풀게되면 두 수의 최소공배수 또한 쉽게 계산이 가능합니다.

 

유클리드 호제법의 알고리즘

두 양의 정수 a와 b가 주어졌을 때, a > b 라고 가정합니다. 유클리드 호제법은 다음과 같이 진행됩니다

 

유클리드 호제법은 a b 크기가 어떻든 상관없이 적용된다!!

 

 

1. a를 b로 나누어 나머지 r을 구합니다. 즉, r = a % b
2. 만약 r = 0 이라면, b가 a와 b의 최대공약수입니다.
3. r != 0 이라면, a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.
4. 즉, GCD(a, b) = GCD(b, r).  (GCD = Greatest Common Divisor, 최대공약수이다.)
5. 이 과정을 r = 0이 될 때까지 반복하면, 그때의 b가 a와 b의 최대공약수가 됩니다.

 

예제

예를 들어, a=252와 b=105가 주어졌을 때, 유클리드 호제법은 다음과 같이 진행됩니다:

1. 252 mod  105=42
2. 105 mod  42=21
3. 42 mod  21=0

따라서 GCD(252,105)=21입니다.

 

 

최대공약수를 이용한 최소공배수 계산

두 수 a와 b의 최소공배수는 다음과 같이 구할 수 있습니다.

 

최소공배수(a,b) = |a x b| / 최대공약수(a,b) 로 구해볼 수 있다.