사단법인 전국수학교사모임
| 단체소개 | 수학과 교육 | 연구팀 | 연수 · 행사 | 자료실 | 지식샘 |
  >  수학용어  >  ㅊ-ㅎ     
유클리드 호제법(-互除法)
sonamy  |  11.10.27 11:05
 132
  조회 3365

 

유클리드 호제법<Euclidean algorithm>(-互除法)

 

최대공약수를 구하는 방법을 말하는 것으로, 유클리드의 저서 《기하학원본》에 기재되어 있다. 간단히 호제법 또는 연제법(連除法)이라고도 한다.

 

• 두 자연수 또는 다항식 a, b의 최대공약수를 구하는 데 있어, 자연수일 때는 a>b, 다항식일 때는 a의 차수가 b의 차수 이상이라 하고, 다음과 같이 나눗셈을 실행한다.

a=[0]#wh4/15.8`6.2/11,[1]{{bq}_{1}`plus`{b}_{1}}…([0]#wh4/4.8`6.2/11,[1]{{q}_{1}}은 몫, [0]#wh4/4.6`6.2/11,[1]{{b}_{1}}은 나머지)

b=[0]#wh4/17.4`6.2/11,[1]{{b}_{1}{q}_{2}`plus`{b}_{2}}…([0]#wh4/4.8`6.2/11,[1]{{q}_{2}}은 몫, [0]#wh4/4.6`6.2/11,[1]{{b}_{2}}은 나머지)

[0]#wh4/27.6`6.2/11,[1]{{b}_{1}`equal`{b}_{2}{q}_{3}`plus`{b}_{3}}…([0]#wh4/4.8`6.2/11,[1]{{q}_{3}}은 몫, [0]#wh4/4.6`6.2/11,[1]{{b}_{3}}은 나머지)

…………………………

[0]#wh4/35.9`6.4/11,[1]{{b}_{n-2}`equal`{b}_{n-1}{q}_{n}`plus`{b}_{n}}…([0]#wh4/5`6.4/11,[1]{{q}_{n}}은 몫, [0]#wh4/4.8`6.4/11,[1]{{b}_{n}}은 나머지)

[0]#wh4/27.1`6.4/11,[1]{{b}_{n-1}`equal`{b}_{n}{q}_{n`plus`1}}([0]#wh4/8.9`6.4/11,[1]{{q}_{n`plus`1}}은 몫, 나머지는 0)

 

이 때, [0]#wh4/4.8`6.4/11,[1]{{b}_{n}}은 처음의 두 자연수 a, b의 최대공약수가 된다고 하는 것을 유클리드의 호제법이라 한다.

• 예를 들어 78696과 19332의 최대공약수를 구하면

78696=19332×4+1368

19332=1368×14+180

1368 =180×7+108

180 =108×1+72

108 =72×1+36

72 =36×2

 

에 따라서, 36이 구하는 최대공약수이다. 실제로 계산할 때는 아래와 같이 두 수를 나열하여 가로선을 긋고, 큰 쪽의 수를 작은 쪽의 수로 나누어 나머지 1368을 낸다. 다음 1368로 19332를 나누어 나머지 180을 낸다. 또, 180으로 1368을 나누어 나머지 108을 낸다. 이와 같이 나눗셈을 거듭 시행해가면 결국 나누어 떨어지며, 그 때의 제수가 최대공약수이다.

  []
의견 쓰기
sonamy님께 이 지식이 도움이 되었다면 추천해주세요!
스크랩  |  주소복사  
더보기
sonamy 2등급
답변파워 3130
tmath_qed 2등급
답변파워 380
test777 2등급
답변파워 335
ncurve 4등급
답변파워 85
lia 4등급
답변파워 80
광고신청  |  사이트맵  |