유클리드의 두 자연수의 최대공약수 구하는 법

유클리드(사진 출처-http://www.mathlove.kr/v2/stories/stories5/index.html)

 

고대 알렉산드리아의 유클리드 Euclid(그리스어: 에우클레이데스 Eukleides)의 ≪원론原論 Elements≫ 제 7권에는 두 자연수의 최대공약수를 구하는 법이 나온다.

두 자연수의 최대공약수란 각각의 약수에서 공통인 가장 큰 수를 뜻한다.

그러나 유클리드는 그 의미에 따라 최대공약수를 구하는 것이 어리석은 행동이라고 말한다.

실제로 수학자들은 일반적인 자연수의 약수를 구하는 일이 매우 어렵다고 생각한다.

 

유클리드는 두 자연수의 최대공약수를 빠르고 쉽게 구하는 방법을 알려주었는데, 유클리드 호제법互除法 Euclidean algorithm이라고  하는 다음과 같은 정리로 표현된다.

호제법이란 두 수가 서로(호互) 상대방 수를 나누어서(제除) 원하는 수를 얻는 알고리즘이다.

우리나라 교과과정에서는 이 유클리드 호제법을 다루지 못하게 되어있으므로, 최대공약수를 구하는 바른 방법은 비밀에 붙여져있는 셈이다.

"자연수 a를 자연수 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다"

 

호제법에서는 큰 수들 사이의 최대공약수를 구하는 문제가 작은 수들 사이의 최대공약수를 구하는 문제로 바뀌고, 다시 같은 이유로 더 작은 수들 사이에서 최대공약수를 구하는 문제로 바뀌는 것이다.

 

그럼 1884와 360의 최대공약수를 호제법을 사용해서 구해보자.

먼저 1884(a)를 360(b)으로 나누면(호제하면),

1884 = 5 × 360 + 84이다.

따라서 1884(a)와 360(b)의 최대공약수는 360(b)과 84(r)의 최대공약수가 된다.

 

두 번째 과정은 작은 수들인 360을 84로 나눈다.

360 = 4 × 84 + 24이다.

따라서 구하는 수는 84와 24의 최대공약수가 된다.

 

세 번째 과정은 더 작은 수들인 84를 24로 나눈다.

84 = 3 × 24 + 12이다.

따라서 구하는 수는 24와 12의 최대공약수가 된다.

 

네 번째 과정은 보다 더 작은 수들인 24를 12로 나눈다.

24 = 2 × 12 + 0이다.

여기서 24는 12의 배수이므로 결국 구하고자 하는 1884와 360의 최대공약수는 12인 것이다.

 

※출처

1. 김홍종 지음, '문명, 수학의 필하모니'(효형출판, 2009).

2. 구글 관련 자료

 

2022. 12. 2 새샘