유클리드 호제법은 두 수의 최대공약수를 구하는 기법이다. 이렇게 구한 최대공약수를 활용하여 두 수의 최소공배수도 쉽게 구할 수 있다.

1. 유클리드 호제법, 최대공약수

gcd(a,b) = gcd(b, a mod b)

[공식 1] 유클리드 호제법

gcd(48, 20) = gcd(20, 8) = gcd(8, 4) = 4 gcd(39, 26) = gcd(26, 13) = 13

[예제 1] 최대공약수 구하기 예제

a, b 두수의 최대공약수를 gcd(a,b) (greatest common divisor)라고 나타낸다면 [공식 1]이 성립한다. a mod b의 값이 0이 될때까지 [공식 1]을 반복하면 쉽게 최대 공약수를 구할 수 있다.

2. 최소공배수

a = G * x, b = G * y G * x * y = (a * b) / G = L

[공식 2] 최소공배수 구하기

39 = 13 * 3, 26 = 13 * 2 13 * 2 * 3 = 78

[예제 2] 최소공배수 구하기 예제

최소배수를 구하려는 숫자를 각각 a, b로 나타내고 a, b의 최대공약수를 G라고 표현하면, a, b의 최소공배수 L은 [공식 2]로 구할수 있다.