*유클리드의 호제법

두 개의 양수 a,b의 최대공약수를 구하는 데에는, 이미 말했던 것처럼, a,b를 소인수분해하면 됩니다. 그러나 이것도 이미 말했던 것처럼, 우리가 책상 위에서 종이와 연필만을 상대하고 있을 때에는 소인수분해는 그리 간단히 되지는 않습니다. 두 개의 양수 a,b의 최대공약수를 구하는 데에, 좀더 실제적인 방법은 '유클리드의 호제법'입니다. 그것은 다음과 같은 방법입니다.

지금 a≥b이고, a를 b로 나눈 몫을 q, 나머지를 r이라 합니다. 즉, a=bq+r, 0≤r0이면, 위의 식에서 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의 최대공약수) = (b,r의 최대공약수) = (r, r1의 최대공약수)가 됩니다. 이 방법을 나누어떨어질 때까지 계속하면, 유한번의 나눗셈에 의해서 반드시 a,b의 최대공약수를 구할 수 있습니다.

위에서 설명한 방법이 유클리드의 호제법입니다. 이것은 옛날부터 알려져 있는 유명한 방법입니다. 사실은 이것도 앞에서 소개한 유클리드의 '원론'이라는 책 속에 이미 확실하게 적혀 있습니다.......

*유클리드의 호제법

두 개의 양수 a,b의 최대공약수를 구하는 데에는, 이미 말했던 것처럼, a,b를 소인수분해하면 됩니다. 그러나 이것도 이미 말했던 것처럼, 우리가 책상 위에서 종이와 연필만을 상대하고 있을 때에는 소인수분해는 그리 간단히 되지는 않습니다. 두 개의 양수 a,b의 최대공약수를 구하는 데에, 좀더 실제적인 방법은 '유클리드의 호제법'입니다. 그것은 다음과 같은 방법입니다.

지금 a≥b이고, a를 b로 나눈 몫을 q, 나머지를 r이라 합니다. 즉, a=bq+r, 0≤r0이면, 위의 식에서 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의 최대공약수) = (b,r의 최대공약수) = (r, r1의 최대공약수)가 됩니다. 이 방법을 나누어떨어질 때까지 계속하면, 유한번의 나눗셈에 의해서 반드시 a,b의 최대공약수를 구할 수 있습니다.

위에서 설명한 방법이 유클리드의 호제법입니다. 이것은 옛날부터 알려져 있는 유명한 방법입니다. 사실은 이것도 앞에서 소개한 유클리드의 '원론'이라는 책 속에 이미 확실하게 적혀 있습니다.......