유클리드의 호제법

요약 유클리드의 저서 《기하학원본》에 기재되어 있는 최대공약수를 구하는 방법으로 호제법 또는 연제법이라고도 한다.

유클리드의 저서 《기하학원본》에 기재되어 있다. 간단히 호제법 또는 연제법(連除法)이라고도 한다. 두 자연수 또는 다항식 a,b의 최대공약수를 구하는 데 있어, 자연수일 때는 a＞b, 다항식일 때는 a의 차수가 b의 차수 이상이라 하고, 다음과 같이 나눗셈을 실행한다.

     a＝bq₁＋b₁… (q₁은 몫, b₁은 나머지)

     b＝b₁q₂＋b₂… (q₂는 몫, b₂는 나머지)

     b₁＝b₂q₃＋b₃… (q₃은 몫, b₃은 나머지)

     ………………………………………

     b_n-2＝b_n-1q_n＋b_n'… (q_n은 몫, b_n은 나머지)

     b_n-1=b_nq_n+1… (q_ńn+1은 몫, 나머지는 0)

이때, b_n은 처음의 두 자연수 a,b의 최대공약수가 된다고 하는 것을 유클리드의 호제법이라 한다.

이를테면, 78696과 19332의 최대공약수를 구하면,

     78696＝19332×4＋1368

     19332＝1368×14＋180

     1368＝180×7＋108

     180 = 108 x 1 + 72     

     108 ＝72×1＋36

     72 ＝36×2

에 따라서, 36이 구하는 최대공약수이다. 실제로 계산할 때는 아래와 같이 두 수를 나열하여 가로선을 긋고, 큰 쪽의 수를 작은 쪽의 수로 나누어 나머지 1368을 낸다. 다음 1368로 19332를 나누어 나머지 180을 낸다. 또, 180으로 1368을 나누어 나머지 108을 낸다. 이와 같이 나눗셈을 거듭 시행해가면 결국 나누어 떨어지며, 그 때의 젯수가 최대공약수이다. 다항식의 경우도 마찬가지로서, 이를테면 두 정식 x³＋6x²＋3x－10, x³＋8x²＋9x－18 의 최대공약수를 구하면 x－1인 답을 얻는다.