<1> 최대공약수와 유클리드의 호제법에 대하여

교수 : 최대공약수에 대하여 설명해볼 수 있겠나?

학생 : 두 개 이상의 정수의 공통인 약수를 그들의 공약수라 하고, 공약수 중에서 가장 큰 수를 최대공약수라 합니다.

이때 최대공약수가 1인 두 정수를 서로소라고 합니다.

이는 다항식에서도 성립하는데 다항식의 최대공약수를 말할 때에는 수인수는 무시하고 생각하는 점이 다릅니다.

최대공약수를 구하는 방법으로는 소인수분해를 이용하여 공통의 약수를 찾은 후 공통의 약수 중 가장 큰 공약수를 찾는 방법이 있는데 쉽게 두 수의 소수인 공약수로 나누어나가는 방법을 사용합니다.

주어진 두 수가 크거나 복잡한 수일 때는 소인수분해를 하지 않고 유클리드의 호제법을 사용하여 간편하게 최대공약수를 구할 수 있습니다.

교수 : 잘 설명하였네. 그럼 방금 이야기한 유클리드의 호제법에 대하여 설명해보게.

학생 : 유클리드의 호제법이란 '자연수 A를 자연수 B로 나눈 몫을 Q,나머지를 R라 할 때 A=BQ+R에서 R≠0이면 A와 B의 최대공약수는 B와 R의 최대공약수와 같다'는 사실을 이용하여 복잡한 수나 다항식의 최대공약수를 구하는 것을 말합니다.

교수 : 매우 중요한 성질을 잘 알고 있군. 그럼 유클리드의 호제법을 증명할 수 있겠나?

학생 : (생각을 정리한 후 답한다.) A, B의 최대공약수를 G라 하면 A=Ga, B=Gb로 나타낼 수 있고 두 수 a, b는 서로소인 수가 됩니다.

여기서 A를 B로 나눈 몫을 Q, 나머지를 R라 할 때 A를 A=BQ+R로 표현할 수 있는데 이 관계식에 위의 A, B식을 대입하면 Ga=Gb·Q+R가 됩니다.

이 식을 정리하면 R=G(a-bQ)가 됩니다. 끝으로 B와 R를 비교해 보면 b와 a-bQ가 서로소이므로 A와 B의 최대공약수인 G는 B와 R의 최대공약수가 됨을 알 수 있습니다.

교수 : 학생은 앞의 증명 과정에서 b와 a-bQ가 서로소라고 했는데 왜 두 수가 서로소인지 설명할 수 있겠는가?

학생 : 앞의 가정에서 두 수 a, b를 서로소인 수라고 하였습니다. 이때 만약 b와 a-bQ가 서로소가 아닌 수라면 두 수 b와 a-bQ는 어떤 공약수 p를 가질 것입니다.

따라서 b=pk, a-bQ=pk'로 나타낼 수 있습니다. 두번째 식을 정리한 후 b에 앞의 식 b=pk를 대입하면,a=bQ+pk'=pk·Q+pk'=p(kQ+k')이 됩니다. 결국 b=pk와 a=p(kQ+k')를 비교해 보면 두 수 a와 b는 p라는 공약수를 가지게 됩니다.

이는 a와 b가 서로소라는 조건에 모순이 됩니다. 이는 결론의 부정으로 인하여 나타난 결과이므로 a, b가 서로소이면 b와 a-bQ도 서로소인 수가 될 수밖에 없습니다.

입력시간: 2002. 03.26. 09:17