유클리드 호제법
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
이 방법은 다항식들의 최대공약수(식)를 구할 때에도 사용됩니다.
뒤의 [다항식의 약수와 배수] 단원에서 공부하도록 합니다.
