약수와 배수(4) 유클리드 호제법

  

유클리드 호제법

Euclidean algorithm

"나머지가 0 이 될 때, 최대공약수가 보여요"

" GCD will be found when the remainder becomes 0 "

유클리드의 호제법은 일반적으로 두 자연수 사이의 최대공약수를 찾아내는 알고리즘 기법입니다.

표준교과의 범위를 벗어 나는 내용입니다만, 소인수로 분해하는 방법보다 빠르고 편리하기 때문에 중, 상위 수준의 학생들이라면 알아 두면 아주 편리하고 빠르게 계산해 낼 수 있습니다.

두 자연수의 나눗셈을 하고 남은 나머지에는, 그 두 수의 최대공약수가 인수로 들어 있다는 원리를 활용하는 개념으로, 심화 수준의 문제 유형에서 그 원리나 응용 개념들이 종종 출제되므로, 보충 설명의 성격으로 게재합니다.

이 유클리드의 기법은 두 정수나 두 다항식의 경우에도 그대로 적용되니, 상위권 학생들은 개념과 원리를 정확히 이해하고, 응용력도 키워두면 좋습니다.

♧   ♧   ♧   ♧   ♧   ♧

이번에는, 두 자연수를 소인수로 분해하지 않고도, 최대공약수를 쉽게 구해 낼 수 있는 '유클리드 호제법' 을 알아 보도록 할까요?

우선, 198 과 120 의 최대공약수를 유클리드 호제법으로 구하는 요령을 단계별로 설명한 다음에 그 원리를 알아 보도록 하지요.

(1) 큰 수를 작은 수로 나누어 몫과 나머지를 구한 후에, 아래와 같이 식으로 적어 놓습니다.

198 = 120 x 1 + 78

(2) 이번에는, 나누었던 수 120 을 나머지인 78 로 나누고 나서, 같은 방법으로 식을 적어 넣습니다.

120 = 78 x 1 + 42

(3) 같은 계산과정을 반복해서, 최종 나머지가 0 이 될 때까지 계속합니다.

78 = 42 x 1 + 36

42 = 36 x 1 + 6

36 = 6 x 6 + 0

(4) 나머지가 0 이 되었을 때의 나누는 수 (또는 그 직전 계산식의 나머지) 인 6 이

     두 수의 최대공약수입니다.

그러면, 도대체 어떤 원리로 최대공약수라고 할 수 있는 것인지, 유클리드 호제법의 원리를 알아 보도록 할까요?

(1) 앞에서, A 를 B 로 나누면, 식으로는 아래와 같이 표현한다고 배웠지요?

A = B x Q + R

(2) 여기서, A 와 B 의 최대공약수를 G 라고 하면, A = a x G 그리고 B = b x G 라 놓을 수 있으니까, 위의 식에다 이를 대입을 하고 나서, 나머지 R 에 관해서 정리하면,

a x G = b x G x Q + R

R = a x G – b x G x Q

= G x (a – b x Q)

∴   R = G x k

(3) 즉, 나머지 R 도 최대공약수 G 의 배수가 된다는 뜻이 됩니다.

2400 년 전에 유클리드가 발견한 이 의미를 식으로 정리해 볼까요?

---

 A = B x Q + R 이라 할 때, A, B 의 최대공약수는, 나누는 수 B 와 나머지 R 의

 최대공약수와 같다.

G (A, B) = G (B, R) 

---

위에서 풀어 보았던 똑같은 문제를 도형의 문제로 바꾸어서 살펴보도록 할까요?

---

 198 x 120 인 직사각형의 바닥을, 정사각형의 타일로 채우려고 한다. 최소의 타일을

 사용하려면, 정사각형 한변의 길이를 얼마로 해야 하는가?

---

(1) 유클리드 호제법을 정사각형들로 이루어진 도형으로 나타내면 아래의 그림과 같습니다.

(2) 위 그림에서 가장 큰 직사각형이 가로가 198, 세로가 120 인 바닥의 크기를 나타냅니다.

     따라서, 첫 번째의 빨간색 정사각형 한 변의 길이는 120 입니다.

(3) 이번에는 가로의 남는 변을 남은 길이인 78 의 파란색 정사각형으로 채워 나가고,

     다음은 남는 세로 길이인 42 의 초록색 정사가형으로 채우고 ...

(4) 이 과정을 계속해 나가면, 위의 그림에서와 같이 마지막으로 주황색의 가장 작은

     6 개의 정사각형으로 채워지게 됩니다. 이 때의 마지막 정사각형 한 변의 길이인

     6 이 최대공약수입니다.

마지막으로, 연습문제를 하나 풀어 보도록 할까요?

---

두 자연수 16082 와 4902 의 최대공약수를 구하여라.

---

두 수가 짝수라는 것 외에는, 쉽게 소인수를 찾아 분해해 내기가 어렵지요? 

이 때에는 [유클리드 호제법] 을 사용하면 쉽습니다.

(1) 큰 수 16082 를 4902 로 나눈다.

16082 = 4902 x 3 + 1376

(2) 유클리드 호제법의 원리에 따라, G (16082, 4902) = G (4902, 1376) = ... 가

     성립한다고 했으니까, 다시 4902 를 1376으로 나눈다.

4902 = 1376 x 3 + 774

(4) 나누어 떨어질 때까지, 같은 방법으로 계속해서 계산해 나가면,

1376 = 774 x 1 + 602

774 = 602 x 1 + 172

602 = 172 x 3 + 86

172 = 86 x 2 + 0

(5) 유클리드 호제법의 원리에 따라서, 최대공약수는 86.

G (16082, 4902)

= G (4902, 1376)

︙

= G (172, 86)

= 86

이 방법은 다항식들의 최대공약수(식)를 구할 때에도 사용됩니다.

뒤의 [다항식의 약수와 배수] 단원에서 공부하도록 합니다.