유클리드 호제법은 두 다항식이나 정수에서 최대공약수를 구하는 방법입니다.

설명

정리 자체는 간단합니다.

1. 두 수 A, B가 존재합니다. 두 수의 최대 공약수를 구해보겠습니다.

2. A를 B로 나눈 나머지가 0이라면 B가 최대공약수입니다.

3. 나누어지지 않는다면 A를 B로 나눈 나머지 R을 구합니다.

4. A와 B의 최대공약수는 B와 R의 최대공약수와 동일합니다.

5. B와 R에 대해 1~4과정을 반복합니다.

증명

증명은 나무위키가 더 잘해주는 것 같습니다.

예시

두 수 84와 120의 최대공약수를 구해보겠습니다.

1. 먼저 120 / 84는 나누어 떨어지지 않습니다. 나머지는 36입니다.

2. 84 / 36은 나누어 떨어지지 않습니다. 나머지는 12입니다.

3. 36과 12는 나누어떨어집니다. 따라서 36과 12의 최대공약수는 12입니다.

4. 84와 36의 최대공약수역시 12이고, 120과 84의 최대공약수도 12가 됩니다.

응용(최소공배수)

최대공약수를 구하면 최소공배수도 구할 수 있습니다.

1. A와 B의 최대공약수를 X라고 하겠습니다.

2. A = X * a, B = X * b라고 표현할 수 있습니다.(a와 b는 서로소)

3. A * B = X * a * X * b입니다. 따라서 A * B / X = X * a * b입니다.

4. 이때 X * a * b는 최소공배수입니다. 따라서 A * B / X(최대공약수)를 계산하면 최소공배수입니다.