유클리드 호제법의 증명~~

안녕하세요 1학년 6반 12번 박광훈입니다~~^^ 이번에 김민기 선생님의 수학사이트에 들어와보고는 "역시 인성고는 달라도 다르구나~~!!"라는 생각을 하게 되었습니다.^^ 여러 친구들의 수학을 향한 집념과 열의를 보고는 나도 더 열심히 해야겠다라는 생각을 새삼 깨닫게 된 것이죠~~^^   다름이 아니라 저번에 김민기 선생님께서 유클리드 호제법에 관하여 말씀을 해주신 적 이 있으셨는데요... 그 때 수업시간에 김민기 선생님께서 "너네들 유클리드 호제법 증명방법 알아왔냐??"라고 물으셨죠~~^^ 그 때 아무도 알아오지 않았다고 하자 선생님께서는 "수학을 잘하는 학생들은 인터넷에서 검색해서 알아온다"라는 말을 듣고 저도 수학을 잘하는 학생이 되어보고자??^^ 인터넷에서 찾아 보았습니다. 이 증명법은 제가 자주 찾아가는 한 수학관련 블로그를 바탕으로 제가 재구성해본 것입니다.   <<유클리드의 호제법>>   먼저 유클리드의 호제법이라는 것을 일반적으로 그냥 호제법 또는 연제법 이라고 부르기도 하는 데 이 유클리드 호제법은 다음과 같습니다. " 두 자연수 또는 두 다항식 A,B의 최대 공약수를 구하는데 있어, 자연수일 경우 A>B이고 다항식일 경우, A의 차수가 B의 차수이상이면  A=B·q+r 에서 A와 B의 최대공약수는 B와 r의 최대공약수와 같다" 라는 걸 말합니다. 여기서 A를 우리는 일반적으로 피제수, B를 제수라고 부르며 q는 몫이 되고 r은 나머지입니다.   그럼 증명 들어갑니다^^ 여기서 A와 B의 최대공약수를 G라고 하면 A=Ga, B=Gb(a 와 b 서로소)라고 표기할 수 있습니다. 물론 다항식일 경우 a 와 b 는 서로 1차 이상의 공통인수를 갖지 않아야 겠죠!!!   A=Ga 이고 B=Gb라고 했으니 A=B·q+r 식에 대입해 봅시다. 그럼 Ga=Gbq+r이 되겠군요~~ 여기서 r에 대해 정리해 봅니다. 우변에는 r만 남기고 모두 좌변으로 이항시켜버리면 되겠습니다. 그러면 r=Ga-Gbq 가 되고 G로 묶게되면 G(a-bq)=r 이 됩니다. 이를 다시 Ga=Gbq+r 식에 대입해 봅니다.   그러면 Ga=Gbq+G(a-bq)가 되게 되겠습니다. 앞에서 유클리드의 호제법이란 피제수A 와 제수B의 최대공약수가 제수B와 나머지 r의 최대공약수와 같다라고 했으므로 A=Ga, B=Gb, r=G(a-bq) 에서 B와 r의 최대공약수는 G가 됩니다. 그런데 어딘가 찜찜한 곳이 남게 되죠~~ 바로 b 와 (a-bq)의 서로소관계의 유무 입니다. 그 어디에도 b 와 (a-bq)가 서로소관계에 있다라고 말하지 않았기 때문이죠. 그렇다면 역으로 b와 (a-bq)가 서로 서로소 관계에 있게 된다면 A와 B의 최대공약수와 B와 r의 최대공약수가 G로 같게 된다는 말인 것이지요~~~ 그러므로 이제는 b 와 (a-bq)의 서로소관계를 입증해 보여야 합니다. 여기서 이를 입증해 보이는 증명법으로는 귀류법을 사용할 겁니다. 귀류법은 모두들 잘 아시죠??? '결론을 부정하여 가정이나 또는 공리(公理)에 모순이 발생하게 되면 그 원 명제가 참이다'라고 간접적으로 증명하는 방법을요^^   그렇다면 우리가 증명해야할 명제는 "위에서의 b 와 (a-bq)가 서로 서로소이다"입니다. 그럼 결론을 부정하게 되면 "만약 b 와 (a-bq)가 서로소가 아니라면" 이 둘은 공약수를 갖게 된다라는 것입니다. 이 때의 공약수를 p라고 하면 "b=p·m, (a-bq)=p·n (m과 n은 서로소)"라고 표현할 수 있습니다.   (a-bq)의 b 자리에 "b=p·m"을 대입해 보면 (a-pmq)가 될 것이며 "(a-pmq)=p·n"라고 할 수 있습니다. 그럼 좌변에는 a 만 남겨두고 모두 우변으로 이항을 시키게 되면 a=pn+pmq 가 될 것이며 p로 묶어서 a=p(n+mq)로 나타 낼 수 있습니다. 그런데 위에 분명 A=Ga, B=Gb 에서 a와 b는 서로소라고 하였는데 a=p(n+mq) 이고 b=pm으로 p라는 수를 공약수로 갖게 되어버립니다. 이로서 모순이 발생됨을 알 수 있습니다. 그럼 원명제 "b와 (a-bq)는 서로 서로소이다"가 참인 명제로 증명되어 졌고, 고로 B=Gb 와 r=G(a-bq)의 최대공약수는 G가 되고 이는 A=Ga 와 B=Gb의 최대공약수 G와 갖게 됨을 알 수 있습니다.   그럼 이와 관련된 문제를 두 문제만 풀어봅시다^^   문제1번)   G( 6438, 20387)을 구하시오 (단, G(A, B) 는 A와 B의 최대공약수를 의미한다.)   일단 6438과 20387이란 숫자를 보게 되면 대부분 "아~~이걸 어떻게 푸나, 수가 너무 커서 짜증이 난다" 등 여러 반응을 보이게 될 것입니다. 하지만 유클리드 호제법의 원리를 알고 있는 똑똑한 학생들은 식은 죽 먹기로 풀 수 있죠^^   먼저 20387을 6438로 나누어 봅니다 그렇게 되면 20387=6438×3+1073 이 됩니다. 앞에서 증명해 보였던 유클리드 호제법에 의하면 20387과 6438의 최대공약수는 6438과 1073의 최대공약수와 같게 되므로 G( 6438, 20387)=G( 6438, 1073) 이 됩니다. 그런데 수가 줄긴 했어도 6438과 1073이란 수는 아직도 우리에게 너무나도 큰 수로만 보여집니다. 그럼 또 나누어 봅니다.    "6438=1073×6+0" 나누어 보니 6438이 1073이란 수로 딱 나누어 떨어지는 군요~~^^ 그럼 G( 6438, 1073)=G( 1073, 0)가 되는군요   그런데 여기서 흠칫 놀라는 학생들이 있을걸로 압니다. 바로 0과의 공약수를 어떻게 찾느냐는 것이지요~~~^^ 그럼 간단히 0을 아무 자연수로나 나누어 봅니다. 그럼 결과는 몫이 0이고 나머지도 0 이 나오게 됩니다. 눈치를 채셨을지 모르겠지만 0은 모든 자연수로 나누어 질때 몫이 항상 0 이고 나머지는 0 입니다. 그럼 0=(모든 자연수)×0+0 이므로 0이 모든 자연수의 배수가 되고 또 모든 자연수는 0의 약수가 됨을 알 수 있습니다. (단, 0을 0으로 나누는 것은 안됩니다)   그렇기 때문에 G( 1073, 0)은 1073이 되겠습니다. 왜냐하면 1073의 약수는 아무리 커봤자 1073이고 모든 자연수는 다 0의 약수이므로 0과 1073이 공통으로 갖고 있는 최대의 약수는 결국 1073이 되는 것이지요~~ 그럼 다음 문제~~~(문제2번은 유클리드 호제법을 다항식에 적용시켜보는 문제입니다)   문제 2번) f(x)=x^4+ax^2+x+2   g(x)=x^3+bx+2 이고 f(x)를 g(x)로 나눈 나머지가 R(x)이다. g(x)와 R(x)의 최대공약수가 "x+2" 일때, ab의 값은????   그럼먼저 다음과 같이 정리 해 볼 수 있겠습니다. x^4+ax^2+x+2=(x^3+bx+2)·Q(x)+R(x)…………………………………………(여기서 R(x)는 차수가 2차 이하인 다항식이나 지금 나머지값을 구하는 것이 아니기 때문에 막연하니 R(x)로 쓰는 것이다)   g(x) 와 R(x)의 최대공약수가 x+2라고 했으므로 유클리드 호제법에 의하여 f(x)와 g(x)의 최대공약수도 그와 똑같은 x+2가 된다. 그럼 x^4+ax^2+x+2=(x+2)·P(x)……1번       x^3+bx+2=(x+2)·S(x)……2번 이므로 1번 식과 2번 식에 모두 x=-2를 대입하여서 " f(-2)=16+4a=0 " 와 " g(-2)=-8-2b+2=0 " 식을 얻게 된다. 그렇게 되면 a=-4 이고 b=-3이 되므로 ab=(-4)×(-3)=12가 된다       모두들 지금까지 읽어주시느라 수고들 많으셨구요^^~~공부하다가 갑자기 생각이 나서 한번 올려봅니다~~^^ 이상한 점 있으면 꼭 답글 남겨주시구요^^~~~지금까지 1학년 6반 12번 박광훈이였습니다~~ 모두들 수학공부 열심히 해서 김민기 선생님을 깜짝 놀래켜 줍시다^^