유클리드 호제법에 대하여 과 목 명 : 수학사 발 표 자 : 수학과 4학년 김은미
유클리드 호제법이란 ? 주어진 두 개의 정수 a, b 에 대하여 a, b 의 최대공약수를 찾는 방법을 말한다. 소인수분해가 쉽지 않은 두 양의 정수나 인수 분해가 쉽지않은 두 다항식의 최대공약수는 유클리드의 호제법을 이용해서 계산하면 쉽게 계산할 수 있다.
예를 들어 a 를 b 로 나누었더니 몫이 q 이고 나머지가 r 이 되었다면 a = bq + r 의 식이 성립한다. 유클리드 호제법의 원리를 간단히 설명하면 두 수가 있을 때 한 수를 다른 수로 나누었을 때의 검산식을 생각해 보자. 예를 들어 a 를 b 로 나누었더니 몫이 q 이고 나머지가 r 이 되었다면 a = bq + r 의 식이 성립한다. 이 때, a 와 b 의 최대공약수는 b 와 r 의 최대 공약수와 같다 (r이 0인 경우에 a 와 b 의 최대공약수는 b가 된다) 라는 것이 유클리드 호제법의 원리이다. 증명을 하기 전에 간단한 예제를 통해 알아보기로 하자...
이 방법을 우리가 흔히 사용하는 방법으로 구해보면… EX) (33, 18)의 공약수를 구하라. 33, 18 의 최대공약수를 d 라고 하면, 33 = 18×1 + 15 이므로 18, 15 의 최대공약수도 d 이다. 18 = 15×1 + 3 이므로 15, 3 의 최대공약수도 d 이다. 15, 3 의 최대공약수는 3 이므로, d = 3 임을 쉽게 알 수 있다. 이 방법을 우리가 흔히 사용하는 방법으로 구해보면… 33 18 33을 18로 나눈다.(몫1,나머지15) 18을 15로 나눈다.(몫1, 나머지3) 15를 3으로 나눈다.(나누어 떨어짐) 마지막 나눗셈의 제수(나누는 수)가 최대공약수 즉, (33, 18)=3 1 1 18 15 15 3 5 15
유클리드 호제법을 증명해보자. a = qb + r ( a,b,q,r은 임의의 정수) a 와 b 의 최대공약수는 b 와 r 의 최대 공약수와 같다 (증명) 우리는 gcd(a,b)=gcd(a-qb,b) 임을 보이면 충분하다. gcd(a,b)=d , gcd(a-qb,b)=s 라고 하자 1) d ≤ s 임을 보일것이다. d I a & d I b & d l qb => d I a-qb 따라서 d는 b와 a-qb의 공약수 S는 a-qb와 b의 최대공약수이므로 d≤s임을 알 수 있다.
2) d ≥ s 임을 보일것이다 s I a-qb & s I b & s I qb => s I (a-qb)+qb=a 따라서 s는 a와 b의 공약수이다. d는 a와 b의 최대공약수이므로 d ≥ s 임을 알 수 있다. 1), 2)에 의해서 d ≤ s , d ≥ s 이므로 d=s
유클리드 호제법 gcd(a,b)=gcd(a-qb,b)을 이용하여 = 37 따라서 gcd(2424869,9509)=37 임을 구할 수 있다.
흔히 사용하는 방법을 써 보자 200 2424869 9509 100 -1901800 -7400 50 523069 2109 20 -475450 -1480 5 47619 629 8 -47545 -592 2 74 37 최대 공약수 -74
참고문헌 www.banyo.ms.kr/no1122/number/uclid.htm <수학의 천재들>, 오승재, 경문사 오른 쪽 아이콘을 누른 뒤 쇼를 마치고 인터넷 메뉴에서 <뒤로>를 누르십시오.