[올림피아드 대비 중등 영재수학]유클리드 호제법

ㆍ두 자연수의 최소공배수·최대공약수 구하기

올해는 기축년 소띠 해이고 지난해는 무자년 쥐띠 해였다. 띠에는 쥐(자), 소(축), 호랑이(인), 토끼(묘), 용(진), 뱀(사), 말(오), 양(미), 원숭이(신), 닭(유), 개(술), 돼지(해) 12가지가 있는데 이것을 12지라 한다. 반면에 10간이라고 하는 것은 갑, 을, 병, 정, 무, 기, 경, 신, 임, 계의 10가지이다. 올해를 나타내는 '기축년'은 10간과 12지를 조합하여 만든 것이다.

먼저 10간의 첫 번째인 '갑'과 12지의 첫 번째인 '자'를 합쳐서 '갑자'가 된다. 가장 최근의 갑자년은 1984년이다. 그 다음해는 10간의 두 번째인 '을'과 12지의 두 번째인 '축'이 합쳐서 '을축년'이 되고, 올해는 10간의 여섯 번째인 '기'와 12지의 두 번째인 '축'을 합쳐서 '기축년'이 되는 것이다. 이 방법을 따라서 여러분이 태어난 해의 간지를 구해 보기 바란다.

이렇게 조합하면 간지는 10과 12의 최소공배수인 60가지가 생기게 됨을 알 수 있다. 따라서 같은 간지의 해는 60년마다 돌아오게 된다. 즉, 1984년이 갑자년이었으므로 다음 갑자년은 2044년이다. 할아버지나 할머니의 회갑잔치를 하는 것을 본적이 있을 것이다. 회갑 이라는 말은 바로 '갑'이 돌아온다는 의미이므로 태어난 지 60년이 되었다는 뜻이다. 따라서 회갑은 61세 때 맞게 된다.

우리 주변에서는 이렇게 최소공배수나 최대공약수가 이용되는 것이 많이 있다. 오늘은 두 자연수의 최대공약수를 구하는 방법과 성질을 알아보자.

자연수 a를 자연수 b로 나누면 a=qxb+r꼴로 나타낼 수 있다. 이 때 q를 몫, r을 나머지라 하는데 나머지는 항상 0보다 크거나 같다. 즉, 0≤r＜b이다. 특히 나머지가 0일 때 a는 b로 나누어 떨어진다고 한다. 자연수 a가 자연수 b로 나누어 떨어질 때 b를 a의 약수, a를 b의 배수라 한다.

두 개 이상의 자연수의 공통인 약수를 공약수라 하고 공약수 중 가장 큰 수를 최대공약수(greatest common divisor)라 한다. 또, 두 개 이상의 자연수의 공통인 배수를 공배수라 하고 공배수 중 가장 작은 수를 최소공배수(least common multiple)라 한다. 공약수 중 가장 작은 수는 항상 이고 공배수 중 가장 큰 수는 없으므로 최소공약수 또는 최대공배수라는 말은 의미가 없다.

두 자연수의 최대공약수를 구하는 가장 기본적인 방법은 두 수를 소인수분해한 뒤 공약수를 찾아보는 방법이다. 위의 예제에서 30=2x3x5, 24=2의3승x3 이므로 최대공약수는 2x3=6이다. 그러나 이 방법은 수가 커지면 아주 복잡하다. 고대 그리스 시대부터 사람들은 이 문제를 해결하기 위하여 고민하였는데, 그 중 한 가지 방법이 유클리드 호제법(Euclid algorithm)이다.

먼저 유클리드 호제법을 이용하여 두 자연수의 최대공약수를 구해 보고, rn이 왜 최대공약수가 되는지 그 이유를 알아보기로 하자.

[예제]

두 자연수 216과 621의 최대공약수를 구하여라. [풀이]

유클리드 호제법에 의하여621=2×216+189216=1×189+27189=7×27+0이므로 최대공약수는 27이다.유클리드 호제법에서 구한 rn이 왜 최대공약수가 되는지 알아보자. 두 자연수 a와 b의 최대공약수를 gcd(a, b)라 나타내자. a=qb+r이라 하면 r=a-qb이므로 gcd(a, b)는 r의 약수이기도 하다. 즉, gcd(a, b)는 b와 r의 공약수이다. k가 b와 r의 공약수라 하면 a=qb+r이므로 k는 a의 약수이기도 하다. 즉, k는 a와 b의 공약수이므로 k≤gcd(a, b)이다. 따라서 gcd(a, b)는 b와 r의 공약수 중 가장 크므로 최대공약수이다. 즉, a=qb+r의 관계가 성립하면

gcd(a, b)=gcd(b, r)임을 알 수 있다. 이제 유클리드 호제법의 식에서gcd(a, b)=gcd(b, r1)=gcd(r1, r2)=…+ gcd(rn-1, rn)이 성립한다.

그런데 rn-1=qn+1 rn이므로 gcd(a, b)=gcd(rn-1, rn)=rn이다.유클리드 호제법을 이용하면 두 자연수 , 의 최대공약수는 적당한 정수 를 이용하여 꼴로 나타낼 수 있다. 이것을 확장된 유클리드 호제법이라 한다. 예제 2의 경우를 보면

27=216+189×(-1)인데 189=621+216×(-2)이므로27=216+[621+216×(-2)]×(-1)=216×5+621×(-1)이다. 이를 이용하여 각자 다음 문제를 풀어보기 바란다. [문제]

두 자연수 , a, b의 최대공약수를 d라 하면 다음이 성립함을 보여라.(1) 임의의 정수 m,n에 대하여 am+bn=dp로 나타낼 수 있다. 여기서 p는 정수이다.

(2) 임의의 정수 p에 대하여 ap=am+bn으로 나타낼 수 있다. 여기서 m, n은 정수이다.

(3) a, b의 최대공약수는 am+bn꼴로 표현되는 가장 작은 자연수이다.< 김병수|서울산업대학교 기초교육학부 교수 >

▲ 정답을 보내주세요

정답을 적어 보내주십시오. 정답자 중 5명을 선정하여 문화상품권(5만원)을 보내드립니다. 정답을 응모할 때 반드시 전화번호, 주소, 이름을 적어주셔야 상품권을 받으실 수 있습니다.

● 정답 올리는 곳 : 시매쓰 홈페이지(www.cmath.co.kr)내 이벤트 게시판

● 응모 기간 : 이벤트 공지 후 다음주 월요일 자정까지

● 정답 및 당첨자 공지 : 응모 마감 후 수요일 오후 2시까지 홈페이지 공지

제공 :

- 대한민국 희망언론! 경향신문, 구독신청(http://smile.khan.co.kr) -ⓒ 경향신문 & 경향닷컴(www.khan.co.kr), 무단전재 및 재배포 금지〈경향닷컴은 한국온라인신문협회(www.kona.or.kr)의 디지털뉴스이용규칙에 따른 저작권을 행사합니다.〉