두 개의 양수 a, b의 최대공약수를 구하는 데에는, 모두들 알고 있는 것처럼, a, b를 소인수분해하면 됩니다.
그러나 이것도 우리가 책상 위에서 종이와 연필만으로 큰 수의 최대공약수를 구하는것은 그리 간단히 되지 않을 수 있습니다. 두 개의 양수 a, b의 최대공약수를 구하는 데에, 좀 더 실질적인 방법은 “유클리드의 호제법" 입니다.
그럼 #유클리드 호제법은 어떤 것인지 알아봅시다.
a ≥ b이고, a를 b로 나눈 몫을 q, 나머지를 r이라 하면.
a=bq+r, 0≤ r <6 입니다. 이 때, 만약 r = 0이라면, 즉 a가 b로 나누어떨어지면, b가 a와 b의 최대공약수입니다.
또, 만약 r >0이면, 위의 식에서 r=a-bq이므로, e를 a, b의 임의의 공약수라 하면, 우변의 a-bq가 e로 나누어떨어지고, 따라서 r이 e로 나누어 떨어집니다.
그러므로 e는 b와 r의 공약수가 됩니다.
한편, e'를 b, r의 임의의 공약수라 하면, a=bq+r이라는 식에서 e`는 a를 나누어 떨어지게 하고, 따라서 e'는 a, b의 공약수가 됩니다. 이것으로 a와 b의 공약수는 b와 r의 공약수이고, 역으로 b와 r의 공약수는 a와 b의 공약수임을 알 수 있습니다.
따라서 "a, b의 공약수 전체의 집합”은 “b, r의 공약수 전체의 집합” 과 일치합니다. 이것으로부터 특히
(a, b의 최대공약수) = (b, r의 최대공약수)
임을 알 수 있습니다.
다음에 b를 r로 나눈 나머지를 r1라 하고, 위에서 설명 한 것과 같은 형태의 이유로, r1=0이라면 r이 b와 r의 최대공약수가 되고, r1> 0 이라면
가 됩니다. 이 방법을 나누어 떨어질 때까지 계속하면, 유한번의 나눗셈에 의해서 반드시 a, b의 최대공약수를 구 할 수 있습니다.
이 방법이 유클리드의 호제법입니다. 이것은 옛날부터 알려져 있는 유명한 방법입니다. 유클리드의 “원론" 이라는 책 속에 소개되어 있습니다.
한 예로서, 247과 962의 최대공약수를 유클리드의 호 제법에 의해 구해 봅시다.
따라서 247, 962의 최대공약수는 13입니다.
위의 계산을 다음과 같은 형식으로 쓸 수 있습니다.
이 계산 방식을 “비(非)자 법"이라고 합니다. 그리고 보니, 한자의 非자와 닮았습니다.
큰수의 최대공약수를 유클리드호제법으로 구하는법을 알아보았습니다.